[백준 Baekjoon] 15486번 퇴사 2 - JAVA

[백준 Baekjoon] 15486번 퇴사 2 - JAVA

---

문제 풀이

다이나믹 프로그래밍을 사용하여 시간복잡도를 O(n)으로 풀어야 하는 문제입니다. 문제에서 주어진 조건 N이 최대 1,500,000으로 시간복잡도가 O(n^2)만 되더라도 시간초과가 발생하게 됩니다. 

 

다음과 같이 다이나믹 프로그래밍을 사용하여 문제를 해결 하였습니다.

int[] dp = new int[N + 1];
int max = 0;

for (int i = 0; i <= N; i++) {
    max = Math.max(max, dp[i]);

    int ni = i + T[i];
    if (ni <= N) {
        dp[ni] = Math.max(dp[ni], max + P[i]);
    }
}

dp[] : 최대 수익을 저장할 배열입니다. 마지막 날에 상담이 완료되는 경우가 발생할 수 있어 N + 1의 크기로 만듭니다.

max : 현재 i날까지의 최대 수익을 저장합니다.

ni : 상담을 완료한 날입니다.

 

상담을 완료한날(dp[ni])의 수익을 현재까지의 최대 수익(max)에 상담 수익(P[i])와 비교하여 최대값으로 갱신합니다.

i의 범위가 최대 N과 같을 때까지 반복을 하는데, 마지막 날에 상담이 완료 될 수 있기 때문입니다.

 

문제의 예제 입력 1의 경우 다음과 같이 dp배열이 갱신됩니다.

0	0	0	10	0	0	0	0
0	0	0	10	0	0	20	0
0	0	0	10	30	0	20	0
0	0	0	10	30	0	45	0
0	0	0	10	30	0	45	0
0	0	0	10	30	0	45	0
0	0	0	10	30	0	45	0
0	0	0	10	30	0	45	45

 

dp[N]일에 최대 수익이 없는 경우가 존재 합니다. 그렇기 때문에 출력 시에는 max값을 출력해줘야 합니다.

 

소스 코드

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

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

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

        int[] T = new int[N + 1];
        int[] P = new int[N + 1];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[N + 1];
        int max = 0;

        for (int i = 0; i <= N; i++) {
            max = Math.max(max, dp[i]);

            int ni = i + T[i];
            if (ni <= N) {
                dp[ni] = Math.max(dp[ni], max + P[i]);
            }

            for (int t : dp) {
                System.out.print(t + " ");
            }
            System.out.println();
        }

        System.out.println(max);
    }
}