백준 15486 : 퇴사 2

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

15486번: 퇴사 2

[ 문제풀이 ]

다이나믹 프로그래밍을 이용한 정해의 시간 복잡도가 O(N)이었기 때문에 다시 한번 풀어봤다. 퇴사 1을 해결한 나의 코드에서 어떤 부분을 줄일 수 있을지 생각해봤다.

​아래의 코드가 퇴사 1에서 O(N^2)의 시간 복잡도를 가지는 구간이다.

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]);
		}
	}
}

굳이 i를 1부터 (i-1)까지 다 확인할 필요가 있을까?

dp[i]에는 항상 최대 수익이 들어있음을 보장해준다. 또한 T의 범위가 최대 50이기 때문에 대략 (i-51)부터 (i-1)까지만 확인해주면 될 것이라고 생각했다. 하지만 (i-51)부터 확인하면 "틀렸습니다"가 떠버렸다...

​N이 최대 1500000이고 시간제한이 2초이기 때문에 넉넉하게 (i-100)으로 잡으니 해결할 수 있었다. 해결은 하였지만 i-51이 안되는 이유는 잘 모르겠다.

for (int i = 2; i <= N; ++i) {
	//T의 최대값이 50이기 때문에 j를 1부터 확인할 필요 x => (i-51)로 하니 틀림
    //N이 최대 150만이기 때문에 150만x100 => 2초 안에 가능 => (i-100)으로 넉넉히 잡음
	int start = Math.max(1, i - 100);
	for (int j = start; j < i; ++j) {
		//j번째 날과 j번째 상담을 하는데 걸리는 기간이 i보다 작거나 같으면
		//i번째 상담하는 비용을 추가시켜줄 수 있음.
		if (i >= j + T[j]) {
			dp[i] = Math.max(dp[i], dp[j] + P[i]);
		}
	}
}

전체 코드는 다음과 같다.

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) {
			//T의 최대값이 50이기 때문에 j를 1부터 확인할 필요 x => (i-51)로 하니 틀림
			//N이 최대 150만이기 때문에 150만x100 => 2초 안에 가능 => (i-100)으로 넉넉히 잡음
			int start = Math.max(1, i - 100);
			for (int j = start; 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();
	}
}

---

이 방법으로 문제를 해결하였지만 정해는 따로 있었다. dp 테이블을 다음과 같이 정의하자.

dp[i] : i번째 전날까지의 최대 수익(i번째 날 상담 x)

간단하게 예시를 통해 점화식을 도출해보자.

dp[1]은 1일전까지의 최대 수익으로 0원이다 => dp[1] = 0
1일날 상담을 하게 돼면 dp[1 + T[1]]의 최대 수익은 10원이다 => dp[4] = 10

dp[2]는 2일전까지의 최대 수익으로 0원이다 => dp[2] = 0
2일날 상담을 하게 돼면 dp[2 + T[2]]의 최대 수익은 10원이다 => dp[7] = 20

dp[3]는 3일전까지의 최대 수익으로 0원이다 => dp[3] = 0
3일날 상담을 하게 돼면 dp[3 + T[3]]의 최대 수익은 10원이다 
=> 현재 dp[4] = 10이기 때문에 갱신 x

dp[4]는 4일전까지의 최대 수익으로 현재 10원이다 => dp[4] = 10
4일날 상담을 하게 돼면 dp[4 + T[4]]의 최대 수익은?
=> 기존의 dp[5]와 dp[4]까지의 최대 수익 + 4일날 상담하는 비용
=> dp[5] = Math.max(0, 10 + P[4]) = 30

dp[i + T[i]]가 될 수 있는 경우는 두 가지이다. 현재 누적된 dp[i + T[i]]와 i번째 날까지의 최대 수익 + i번째 날 상담 비용, 둘 중 최댓값이다.

따라서 다음과 같은 점화식을 도출해낼 수 있다. i번째 날까지의 최대 수익을 빠르게 구하기 위해 max라는 변수에 저장하여 관리한다.

​또한, 우리는 N+1날에는 퇴사를 하기 때문에 dp[N+1]까지 구해야 한다. 따라서 i + T[i]가 N + 1보다 크다면 구할 필요가 없다.

for (int i = 1; i <= N + 1; ++i) {
	//i번째 이전 까지의 최대 수익
	max = Math.max(max, dp[i]);
			
	//N + 1날에는 퇴사하기 때문에 x
	if (i + T[i] > N + 1) continue;
		
    //dp[i + T[i]] vs i 번째 날까지의 최대 수익(max) + i 번째 날의 상담 비용
	dp[i + T[i]] = Math.max(max + P[i], dp[i + T[i]]);
}

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

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, max;
	static int[] T, P, dp;

	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		T = new int[N+2];
		P = new int[N+2];
		dp = new int[N+2]; //dp[i] : i번째 전날까지의 최대 수익(i번째 날 상담 x)

		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;
		}

		for (int i = 1; i <= N + 1; ++i) {
			//i번째 이전 까지의 최대 수익
			max = Math.max(max, dp[i]);

			//N + 1날에는 퇴사하기 때문에 x
			if (i + T[i] > N + 1) continue;

			//dp[i + T[i]] vs i 번째 날까지의 최대 수익(max) + i 번째 날의 상담 비용
			dp[i + T[i]] = Math.max(max + P[i], dp[i + T[i]]);
		}

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