[백준] 14501번 : 퇴사

문제

 

 

접근 방식

문제에 나와 있는 예시를 살펴보면

4일의 경우에는 1일과 3일 중 하나를 선택할 수 있고

둘 중 더 큰 값을 선택하는 것이 효율적이니

더 큰 값을 골라주면 된다. (예시에서 두 날의 값은 같아서 뭘 고르든 상관은 없다.)

 

즉, 현재 날을 기준으로 이전에 상담이 끝나는 요일들 중

가장 비용이 큰 값을 선택해주면 된다.

 

DP 테이블은 아래와 같이 정의했다.

dp[i] = i번째 날에 받을 수 있는 누적 금액

 

dp[i] = 1 ~ i-1까지의 날짜 중 i일 이전에 끝나고 가장 비용이 큰 값

위의 과정을 코드로 작성하면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());

		int[] times = new int[n + 1];
		int[] prices = new int[n + 1];

		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());

			times[i] = Integer.parseInt(st.nextToken());
			prices[i] = Integer.parseInt(st.nextToken());
		}

		int[] d = new int[n + 1];
		int result = 0;

		for (int i = 1; i <= n; i++) {
			if (i + times[i] - 1 > n) continue;

			int max = prices[i];

			for (int j = 1; j < i; j++) {
				if (j + times[j] - 1 < i) max = Math.max(prices[i] + d[j], max);
			}

			d[i] = max;
			result = Math.max(max, result);
		}

		System.out.println(result);
	}
}