[PS] 백준 14501번: 퇴사

|

문제

내가 이해한 문제 내용

주어진 기간 $n$이 있고 각 날짜에 상담을 했을 때 버는 돈과 상담기간이 있을 때 $n$일 내에 상담을 해서 벌 수 있는 돈의 최댓값을 구하여라.

접근 방식

DP이기 때문에 점화식을 짜려고 시도했으나 처음에 애초에 잘못 접근을 했다. 상담을 한 경우와 안한 경우를 나눠서 각 경우에 대해 봤다. 다음과 같이 점화식을 짰다.

DP[i][0]=i번재 날에 상담을 안한 경우, DP[i][1]=i번째 날에 상담을 한 경우

따라서 특정 날짜에서 이전 날짜를 탐색하면서 각 날짜의 상담을 한 경우와 안한 경우 중 최댓값을 선택하는 것이다. 근데 이럴 경우 문제점이 어떤 특정 날을 보고 최댓값을 선택했는데 그 최댓값을 가지는 상담 날짜의 상담기간이 현재 날짜를 넘어버리는 것이었다. 결국 점화식을 잘못 짰다는 것을 깨달았고 찾아보니 DP[i] = i번째 날까지 얻은 최대이익으로 점화식을 짜면 간단하게 풀리는 것이었다.

왜일까? 해당 점화식이 적용되는 반복문 안에서 유효성(상담이 가능한지)을 확인해주면 그 날짜까지의 최대이익을 계산할 수 있고 DP라서 연쇄적으로 이어지기 때문이다. 애초에 DP의 핵심이 이전에 얻은 값을 활용하는 것인데 그 부분을 놓쳤다.

어려웠던 점 & 배운 점

제발 생각하지 말고 최대/최소 그니까 그리디로 접근하지 말자. 그리고 이전 값들을 활용하자.

시간복잡도

이전 날짜를 모두 확인하니까 $O(n^2)$

코드

#include <cstdio>
#include <algorithm>

int n;
int d[16],c[16],dp[16];

int main(void)
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        scanf("%d%d",&d[i],&c[i]);
        if(i+d[i]<=n+1) dp[i] = c[i];
    }

    int ans = dp[1];
    for(int i=2; i<=n; i++){
        if(i+d[i]>n+1) continue;
        for(int j=1; j<i; j++){
            if(j+d[j]<=i)
                dp[i] = std::max(dp[i],dp[j]+c[i]);
        }
        ans = std::max(ans,dp[i]);
    }

    printf("%d", ans);
    return 0;
}