백준 14501 : 퇴사

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

14501번: 퇴사

[ 문제풀이 ]

정해는 다이나믹 프로그래밍이지만 N이 워낙 작기 때문에 완전 탐색을 기반으로 해결해도 되는 문제이다. 나는 다이나믹 프로그래밍을 이용해서 해결하였다.

​먼저 다음과 같은 dp 테이블을 정의하자.

dp[i] : i번째 날 얻을 수 있는 최대 수익

위와 같은 정의를 통해 우리는 dp[i]는 최대 수익이 들어있다고 가정할 수 있다. 그렇다면 점화식은 어떻게 도출할 수 있을까?

​j번째 날과 j번째 상담을 하고 걸리는 기간(T[j])이 현재 i번째 날보다 작거나 같으면 j번째 날의 최대 비용에 i번째 날의 상담을 하는 비용을 추가해 줄 수 있다.

​따라서 다음과 같은 점화식을 도출해 낼 수 있다.

for (int i = 2; i <= N; ++i) {
	for (int j = 1; j < i; ++j) {
		if (i - j - T[j] >= 0) {
			dp[i] = Math.max(dp[i], dp[j] + P[i]);
		}
	}
}

마지막으로 N+1일째 날에 퇴사를 하기 때문에 i번째 날 + i번째 상담을 하고 걸리는 기간(T[i]) 값이 N+1보다 작거나 같아야 한다.

​최종적인 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int N, answer;
	static int[] T, P, dp;

	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		T = new int[N+1];
		P = new int[N+1];
		dp = new int[N+1]; //dp[i] : i번째 날 얻을 수 있는 최대 수익

		for (int i = 1; i <= N; ++i) {
			st = new StringTokenizer(br.readLine());
			int t = Integer.parseInt(st.nextToken());
			int p = Integer.parseInt(st.nextToken());

			T[i] = t;
			P[i] = p;
			dp[i] = p;
		}

		for (int i = 2; i <= N; ++i) {
			for (int j = 1; j < i; ++j) {
				//j번째 날과 j번째 상담을 하는데 걸리는 기간이 i보다 작거나 같으면
				//i번째 상담하는 비용을 추가시켜줄 수 있음.
				if (i >= j + T[j]) {
					dp[i] = Math.max(dp[i], dp[j] + P[i]);
				}
			}
		}
		
		for (int i = 1; i <= N; ++i) {
			//퇴사일 N+1을 넘기면 안됨
			if (i + T[i] <= N + 1) {
				answer = Math.max(answer, dp[i]);
			}
		}

		bw.write(answer + "\n");
		bw.flush();bw.close();br.close();
	}
}

나는 O(N^2)의 시간 복잡도로 해결하였는데 정해는 O(N)의 시간 복잡도라고 한다. 백준 15486번(퇴사 2)은 O(N)의 시간 복잡도로 해결해야 통과할 수 있다.

​O(N)으로 시간 복잡도를 줄일 수 있는 방법을 한 번 고민을 해봐야겠다.