[백준] Gold V. 퇴사2

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

 

 

사용 알고리즘

• 다이나믹 프로그래밍

 

풀이

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

/*
    테이블: d[i]: i번째 날에 받을 수 있는 최대 금액
    점화식: d[j]: Math.max(d[j], d[i] + money)
 */
public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[] t = new int[n + 1];
        int[] p = new int[n + 1];
        int[] d = new int[n + 2];

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

        }

        for(int i = 1; i <= n; i++) {
            int day = t[i];
            int money = p[i];
            if (i + day <= n + 1) {
                d[i + day] = Math.max(d[i + day], d[i] + money);
            }
            d[i+1] = Math.max(d[i+1], d[i]);
        }

        System.out.println(d[n+1]);

    }
}

 

 

회고

답과 근접하게는 풀었는데, 예제 4번에서 틀려서 답안을 참고하게 됐다.

 

10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

 

답: 90

 

이렇게 예제가 존재할때, 1번째 -> 6번째 -> 7번째로 가서 (50 + 10 + 20) = 80이 아닌가? 계속 고민했다.

 

내가 놓쳤던 부분은 두가지인데,

 

첫번째로,

상담을 할 때 당일을 포함시켜줘야 한다.

8	9	10
3	4	5
30	40	50

 

8일차에서 나는 상담을 하면 11일로 이동을 하기 때문에 사용할 수 없다고 생각했다. 하지만, 당일을 포함 한다면, [8,9,10]이렇게 상담을 진행할 수 있다.

 

두번째로,

 

d[i+1] = Math.max(d[i+1], d[i]);

 

현재 시점가지의 최대 수익을 계속 갱신해주어야 한다.

 

갱신을 해주지 않았을 떄:

0 0 0 0 0 0 50 60 0 80 0 30

 

갱신해줄 때:

0 0 0 0 0 0 50 60 60 80 80 90

 

갱신을 해주지 않을 떄 8일차에 상담을 할 떄 이전값이 저장되어 있지 않기 때문에 90이 아닌 30이 저장된다. 

 

두가지 다음에 실수하지 않도록 주의해야겠다.