백준 #15486 퇴사2

오늘은 초등학교 동창이자 대학 동기인 이ㅇㅇ군 과 함께 스타벅스에서 공부를 하게 되었다. 함께 공부를 잠깐 하다 같이 알고리즘 1문제를 풀어보기로 하였고, DP문제가 구현이 쉽다 주장하는 이ㅇㅇ군의 의견을 적극 반영해 DP문제를 함께 풀게 되었다. 열심히 문제를 풀던 와중, 스타벅스 직원이 와서 2인 이상은 1시간 밖에 이용이 안되니 나가달라고 하였다. 거의 다 풀었다 생각했는데 중간에 쫓겨나게 된 우리는 아쉬움을 달래기 위해 코인노래방에서 잠깐 노래를 부르고 집에 왔다. 하지만 알고보니 난 거의 다 푼것이 아니었다. 내가 잘못 접근하고 있던 방식이 내가 대부분의 DP문제를 풀 때 접근하는 방식이었기 때문에 그렇게 풀면 안된다는 사실을 깨닳았던 좋은 문제였다. 

 

DP배열에는 그 날까지 최대로 얻을 수 있는  수익이 저장된다.

DP배열을 만들고 첫 입력부터 시작해 이전에 저장되어 있던 DP의 값과 현재 DP값과 이익을 비교하여 후자가 더 크다면 DP값을 변경해주었다. 하지만, 이렇게 하면 (1) 첫 입력부터 마지막까지 for문을 한바퀴 돌고, 그 위치에서(2) T일 후 종료되는 시점부터 DP값을 비교해주어야 하기 때문에 for문을 한바퀴 더 돌아야 한다. 이 때 최악의 경우 n! 까지도 걸리는거 같다.(확실하지는 않다) 대참사다!

 

이 문제를 해결하기 위해 떠올린 방법은 바로 맨 뒤에서부터 DP값을 변경해오는 것이다.

 

각 Ti, Pi 값을 벡터로 저장이 되어있다. 

for(int i=n-1; i>=0; i--)
    {
        if(i + list[i].first > n )
        {
            dp[i] = dp[i+1]; //현재 위치에서 상담하는데 걸리는 일수를 더한 값이 퇴사하는 날보다 뒤라면 dp 값은 그 다음날것과 같다.
        }
        else
        {
            dp[i] = max(dp[i+ list[i].first] + list[i].second , dp[i+1]);
            //dp값은 그 다음날의 dp값과 현재 날 일할 때 받을 수 있는 금액과 그 일이 끝난 날의 dp 값의 합 중 더 큰 값으로 정해진다.
        }
    }

벡터 가장 끝에서부터 시작하고, 해당 날에 일을 시작했을 때 퇴사하는 날 전에 일이 끝나지 않는다면 그 날의 DP값은 그 다음날의 DP값과 같다. 해당일에 시작하는 일은 할 수 없기 때문이다. 

그렇지 않다면 그 날의 DP는 그 다음날의 DP값과,  그 날 일의 이익과 그 일이 끝나는날의 DP값의 합 중 더 큰 값으로 하면 된다!

그럼 첫날 DP에 얻을 수 있는 최대수익이 저장된다.

 

DP문제는 방법을 알면 쉽다고 생각했었는데 이번에는 어떻게 하면 되는지는 알았는데 생각을 한 번 더 해야했다. 그래서 시간이 오래걸리고 헤맸다.  다음번에 이런 유형의 DP문제를 만나게 되면 한 번 더 생각을 해볼 수 있을 것 같다.