[백준 BOJ] 14501 퇴사(DP/자바)

문제 접근 방법

1. DP

2. 현재 일 수 + 상담에서 걸리는 시간(Ti)가 N+1보다 크면 퇴사하므로 상담을 할 수 없습니다. 따라서, 이에 대한 경우 0으로 세팅했습니다.

3. 1일을 선택하면 4일이 되어야 4일-1일 >= 3일이 되므로 4일 최대 금액은 4일 금액 + 1일 금액이 됩니다.

 

점화식

- 현재 일수에서 나올 수 있는 최대 금액 = Math.max(현재 일 수 금액, 현재 전까지에서 나올 수 있는 일수 금액 중 최대);

- dp[i] = Math.max(dp[i], dp[j] + prices[i])

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = Integer.parseInt(br.readLine());
		
		int[] times = new int[N+1];
		int[] prices = new int[N+1];
		int[] dp = new int[N+1];
		
 		for (int i = 1; i < N+1; i++) {
 			st = new StringTokenizer(br.readLine());
 			times[i] = Integer.parseInt(st.nextToken());
 			prices[i] = Integer.parseInt(st.nextToken());
 			dp[i] = prices[i];//미리 상담 금액으로 세팅
		}
 		 		
 		
 		for (int i = 1; i < N+1; i++) {
 			if(i+times[i] >= N+2) {
 				dp[i] = 0;
 				continue;
 			}
			for (int j = 1; j < i; j++) {
				if(i-j >= times[j]) {
              		//현재 일수 = 기존 상담 금액과 그 전에 선택했던 일수에 대한 최대 비교
					dp[i] = Math.max(dp[i], dp[j] + prices[i]);
				}
			}
		}
		
 		int result = Integer.MIN_VALUE;
 		for (int i = 1; i < N+1; i++) {
			result = Math.max(result, dp[i]);
		}
 		
 		System.out.println(result);
	}
}

 

 

 

 

문제 

https://www.acmicpc.net/problem/14501