[백준] 15486 퇴사 2

Posted on | In

다시 dp 문제를 잡았다. 나 혼자 dp 문제를 해결할 수 있다는 사실이 참 신기한데, 이 문제에서는 혼자 풀었다가 시간초과가 났다. 따라서 내 풀이를 먼저 설명하고, 그 다음으로 실제 풀이는 어떻게 진행되는지 설명해보려고 한다.

문제 설명

링크 이 문제는 해당 업무를 처리하는 데 걸리는 시간과 성과금을 주고, 어떤 업무들을 선택했을 때 총 성과금이 최대가 되는지를 묻는 문제이다. 그래서 특정 업무를 처리하는 데 3일이 걸리면, 그 3일동안은 다른 업무를 처리할 수 없다.

나의 첫 문제 풀이

나는 dp[i] 배열을 정의해서 i번째까지 갔을 때 최대 성과금을 저장하도록 했다. 따라서 dp[i]는 0번째부터 i-1까지 중에서 최대 성과금(dp[0]~dp[i-1])이 가장 큰 것을 선택해야 한다. 여기서 주의해야 할 점은, i번째까지 갔을 때 그 직전에 선택한 업무가 끝나있는가 이다. 업무가 끝나 있지 않다면 나는 i번째까지 갔을 때 i번째 업무를 처리할 수 없고(dp[i]에 p[i]를 더해줄 수 없고) 업무가 끝나 있다면 dp[i], 최대 성과금에 i번째 업무를 더 진행할 수 있다. 따라서 결국 이중포문을 돌게 되는데, 이래서 시간초과가 난 것 같다. 그런데 지금 체크해 보니 퇴사 1도 틀렸다고 나온다. 풀이 자체가 어디선가 오류가 있는 듯 하다. 약간만 수정을 해주면 될 것 같으니까 내일 퇴사 1로 다시 포스팅 해보겠다!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
int n;
int t[1500001];
int p[1500001];
int dp[1500001];

int main(){
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%d %d", &t[i], &p[i]);
        dp[i]=0;
    }

    dp[0]=p[0];
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            if(dp[i]<dp[j]+p[i] && t[j]+j<=i && t[i]<=n-i){
                dp[i]=dp[j];
                dp[i]+=p[i];
            }
            else if(dp[i]<dp[j]) dp[i]=dp[j];
        }
    }

    int max=0;
    for(int i=0;i<n;i++) if(max<dp[i]) max=dp[i];
    printf("%d\n", max);
}

시간초과가 안 나는 dp 문제 풀이

이중포문을 사용하지 않으면 for문을 뒤에서부터 돌면 해결할 수 있다. (이 생각을 어떻게 했나 모르겠다) 링크 풀이를 생각하는 방식은 위에 내가 했던 것과 비슷한데, 조금 다른 점은 i번째 날 업무를 진행했을 때랑 진행하지 않았을 때를 비교해서 더 큰 값을 사용한다는 것이다. 그래서 생각해야 할 점은 i번째 날 업무를 진행하면 퇴사날 이후에 끝나서 업무를 진행하면 안될 때와(i+t[i]>n), 그렇지 않은 경우에 i번째 날 업무를 진행하거나 진행하지 않거나를 따지는 것이다. i번째 날에 업무를 진행하게 되면 t+t[i]날의 최대 성과금에다가 i번째 날 업무에 대한 성과금을 더한 만큼을 최종 성과금으로 얻게 되고, i번째 날에 업무를 진행하지 않으면 i+1번째 날의 최대 성과금과 i번째 날의 최대 성과금이 동일해지게 된다. 이것을 이용해서 뒤에서부터 for문을 돌면 된다. 너무 신기하다.! 내일은 퇴사 1 문제를 이중포문으로 풀어봐야겠다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <algorithm>
using namespace std;

int n;
int t[15000001];
int p[15000001];
int dp[15000001];

int main(){
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%d%d", &t[i], &p[i]);
        dp[i]=0;
    }
    dp[n]=0;

    for(int i=n-1;i>=0;i--){
        if(i+t[i]>n) dp[i]=dp[i+1];
        else{
            dp[i]=max(dp[i+t[i]]+p[i], dp[i+1]); // 그날 업무 하는 거랑 안하는 것 중에 큰 것 고르기.
        }
    }

    printf("%d\n", dp[0]);
}