백준 14501번 퇴사 [DP] :: 마이구미

이 글은 백준 알고리즘 문제 14501번 "퇴사" 를 풀이한다.

삼성 SW 역량 테스트의 기출 문제이다.

동적계획법을 통해 문제를 해결할 수 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일 째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이 때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

문제에서 힌트를 얻을 수 있다.

예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

이것만 이해했다면, 문제를 이해한 것이다.

위에서의 최대 이익은 1, 4, 5일이 된다. (문제에서 나오지는 않았지만, 3, 4, 5일도 가능하다.)

본인은 단순하게 점화식을 도출했다.

dp[N] = N일까지 얻는 이익

N일을 기준으로 N일 이전에 얻을 수 있는 경우를 모두 비교하면 된다.

dp[i] = Max(p[i] + dp[j], dp[i]) // i - 기준일, j - (1 ~ i-1)일

dp[5] = Max(5일의 이익 + 1일까지의 이익, 5일까지의 이익)

dp[5] = Max(5일의 이익 + 2일까지의 이익, 5일까지의 이익)

dp[5] = Max(5일의 이익 + 3일까지의 이익, 5일까지의 이익)

dp[5] = Max(5일의 이익 + 4일까지의 이익, 5일까지의 이익)

위와 같이 갱신된 dp 배열의 값을 이용하면서, 계속 갱신해나간다.

무작정 갱신하면 안되니, 힌트를 토대로 조건을 성립시키면 된다.

private void solve() {
    int n = sc.nextInt();
    int[] t = new int[n + 1];
    int[] p = new int[n + 1];
    int[] dp = new int[n + 1];
 
    // http://mygumi.tistory.com/151
 
    for (int i = 1; i <= n; i++) {
        t[i] = sc.nextInt();
        p[i] = sc.nextInt();
 
        dp[i] = p[i];
    }
 
    // dp[n] = n일때까지 얻은 수익
 
    for (int i = 2; i <= n; i++) {
 
        for (int j = 1; j < i; j++) {
 
            if (i - j >= t[j]) {
                dp[i] = Math.max(p[i] + dp[j], dp[i]);
            }
 
        }
 
    }
 
    int max = 0;
 
    for (int i = 1; i <= n; i++) {
        if (i + t[i] <= n + 1) {
            if (max < dp[i]) {
                max = dp[i];
            }
        }
    }
    System.out.println(max);
}