[C++]15486: 퇴사 2

요약

bottom-up 방식이면 O(n)으로 가능하고, top-down이면 O(n^2)

풀이과정

일단 시간복잡도를 가늠해보면 n은 150만이다.

O(n^2) 불가능하고, O(nlongn), O(n)정도 가능해 보인다.

 

수익의 최대는 일단 고려하지 않는다면, 아래와 같이 생각할 수 있다.

내가 오늘 상담을 한다면? : 이 상담이 끝나는 날 : 오늘 수익 + 오늘 상담 수익

내가 오늘 상담을 하지 않는다면? : 아무것도 변하지 않음

 

i번째 날 수익을 버는 경우의 수는 다양하며, 이 경우의 수 중에서 최대의 수익을 버는 경우를 고려하려면...

최대 수익을 저장하는 행렬(이든 벡터든) dp에 접근할때마다 max값으로 갱신한다.

내가 오늘 상담을 한다면? : dp[상담끝나는날] = max(기존수익, 오늘수익+오늘상담수익)

 

문제는 내가 오늘 상담을 하지 않는다면? 이다.

이것도 똑같이 생각하면 된다. 오늘 일하지 않는다는 것은, 내일 수익이 오늘 수익과 같다는 것이다.

내가 오늘 상담을 하지 않는다면? :  dp[내일] = max(기존수익, 오늘수익)

 

그러면 1일부터 n일까지 한번씩 해주면 되니까 O(n)만에 문제 해결이 가능해진다.

O(n)이 되는 이유는 이 문제의 특성 상, 1일부터 n일까지 순서대로 채우면 무조건 max값이 보장된다는 점 때문이다

(미래의 값이 과거에 영향을 줄 수 없음 - 시간의 특성이 반영된 문제)

그게 아니면 모든 경우의 수를 고려해야하니 O(n^2)이 걸렸겠지?

 

그리고 상담을 하는 경우, 벡터 범위를 뛰쳐나갈수 있으니 상담이 끝나는 날이 n+1일 이하인경우만 계산하게끔 해줘야 런타임 에러가 발생하지 않음

코드

//https://www.acmicpc.net/problem/15486
#include <iostream>
#include <vector>

using namespace std;
vector<int> schedule;
vector<int> pay;
vector<int> dp;


int main()
{
    int n;  scanf("%d", &n);
    schedule.resize(n+1,0);
    pay.resize(n+1,0);
    dp.resize(n+2,0);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d",&schedule[i], &pay[i]);
    }

    for(int i = 1; i <= n; i++)
    {
        //상담을 한다면
        if(i+schedule[i] <= n+1)
            dp[i+schedule[i]] = max(dp[i+schedule[i]], dp[i]+pay[i]);
        //상담을 하지 않는다면
        dp[i+1] = max(dp[i+1],dp[i]);
    }

    printf("%d",dp[n+1]);
    return 0;
}

기억할 점

 

다른 사람의 풀이