[ 백준 15486 ] 퇴사2 (C++)

백준의 퇴사2(15486) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 퇴사1과 동일한 조건에 똑같은 문제이지만 N의 범위가 150만으로 퇴사1에서 사용했던 방법인 완전탐색으로는

   절대 시간내에 통과할 수 없다.

   따라서 본인은 이 문제에서는 Dynamic Programming 방식을 사용해서 접근해보았다.

   DP과정을 위해서 DP[] 라는 배열을 하나 선언해 주었다.

   DP배열에 저장되는 값은 "현재 시점까지 벌 수 있는 최대 액수"를 의미한다.

   조금 더 구체적으로 말해보자면 DP[a] = b 이다 의 의미는 "a일 까지의 최대 액수는 b원입니다"가 된다.

   여기서 주의해줘야 할 것은 DP[a] 에서 a가 의미하는 것은 그 날 까지가 아닌, 그 전날까지를 의미한다.

   즉, DP[4] = 10 이라고 했을 때, 4일까지 일을 했을 때 벌 수 있는 돈을 의미하는 것이 아니라, 4일전까지, 즉

   1 ~ 3 일동안 벌 수 있는 최대 액수를 의미한다. 더욱더 쉽게 생각하면, 일을 한 후에 돈을 받는다고 생각하면 된다.

  

2) 구체적인 풀이에 들어가보자.

   이해하기 쉽게 문제에 주어진 예제입력 1을 예제로 삼아서 풀어 나가보자.

  

   예제입력1의 일정표이다.

   먼저 DP[1]의 값을 생각해보자. DP[1]이라는 것은 "1일전까지 일을 해서 벌 수 있는 최대 액수"를 의미한다.

   당연히 0원일 것이다. 그럼 1일날 일을 하게 된다면, 언제 돈을 받게될까? 위에서 말한것 처럼 일을 한 후에

   돈을 받는 개념으로 접근해보면, 4일날 받을 수 있음을 알 수 있다.

   그럼 우리는 1일을 계산하면서 DP[4]의 값을 갱신할 수 있다. DP[4] = 10으로 갱신될 것이다.

   다시한번 정리해보자면, "1일날 일을 함으로써 돈은 3일후인 4일날 받을 수 있다. 따라서 4일까지 벌 수 있는

   최대액수는 10원이다" 라는 것을 알 수 있게 되는 것이다.

   2일로 가보자. 현재 2일까지 일을 해서 벌 수 있는 최대 금액은 0원이다.

   2일날 일을 하면 돈을 7일날 받게 될 것이다. 즉, DP[7] = 20 이라고 우리는 갱신할 수 있다.

   3일로 가보자. 현재 3일까지 일을 해서 벌 수 있는 최대 금액은 0원이다.

   3일날 일을 하면 4일날 받게 될 것이다. 그럼 4일까지 벌 수 있는 최대 액수는 얼마일까 ??

   지금 현재 '1일'에 의해서 4일까지 벌 수 있는 액수가 10원이라는 것을 알고 있다. 하지만, '3일'날 일을

   한다고해서 10원보다 더 큰 액수를 벌 수 있는 것은 아니므로 그대로 DP[4] = 10으로 유지될 것이다.

   4일로 가보자. 현재 4일까지 일을 해서 벌 수 있는 최대 금액은 10원이다.

   4일날 일을 하게 되면 5일날 받게 될 것이다. 그럼 5일까지 벌 수 있는 최대 액수는 얼마일까 ??

   5일날 벌 수 있는 최대액수는 둘 중 하나일 것이다.

   1. 4일까지 일을 해서 벌 수 있는 최대 액수 + 4일날 일을 함으로써 벌 수 있는 돈

   2. 기존에 설정된 5일까지 일을 해서 벌 수 있는 최대액수

   두개 중에 하나일 것이다. 1번 같은 경우, 4일까지 일을해서 벌 수 있는 최대액수 = 10 + 4일날 일을 함으로써 벌 수 있는

   돈 = 20 이 되어서 30원이 될 것이고, 2번 같은 경우 아직 5일은 벌 수 있는 돈이 없으므로 0원일 것이다.

   즉, DP[5] = 30으로 갱신될 것이다.

   위와 같은 방식으로 탐색을 해주면 된다. 단, 일을 함으로써 받게 되는 돈의 날짜가 N + 1 보다 커져버리면

   그 일은 할 수 없다.

   왜냐하면, N + 1일까지의 값을 계산을 하면 N일까지 일을 했을 때의 최댓값을 구할 수 있지만, 그 이상은 퇴사를

   하기 때문에 돈을 못받기 때문이다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 1500010
using namespace std;
 
int N, Answer;
int DP[MAX];
int Arr[MAX][2];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Arr[i][0] >> Arr[i][1];
    }
    // Arr[i][0] = 걸리는 날짜
    // Arr[i][1] = 돈
}
 
void Solution()
{
    int Current_Max = 0;
    for (int i = 1; i <= N + 1; i++)
    {
        Current_Max = Bigger(Current_Max, DP[i]);
        if (i + Arr[i][0] > N + 1) continue;
        
        DP[i + Arr[i][0]] = Bigger(Current_Max + Arr[i][1], DP[i + Arr[i][0]]);
    }
    Answer = Current_Max;
}
 
void Solve()
{
    Input();
    Solution();
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}