[ 백준 14501 ] 퇴사(Ver2) (C++)

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

[ 문제 바로가기 ]

(본 문제는 백준의 퇴사2(14586) 문제에 대한 풀이가 아닌 , 퇴사(14501) 문제에 대한 두 번째 풀이입니다.

 관련된 풀이를 원하시는 분들은 아래 링크를 이용해 주세요.

 퇴사2(14586) 풀이 보러가기 → [ 퇴사2(14586) 풀이 바로가기 ]

 퇴사(14501) 첫 번째 풀이 보러가기 → [ 퇴사(14501) 풀이 바로가기 ] )

[ 문제풀이 ]

퇴사에 대한 풀이 글이 위에 걸어놓은 링크처럼 있는데, 위의 글에서는 이 문제를 재귀를 이용한 완전탐색 방식으로 구현하였다.

이 글에서는 이 문제를 Dynamic Programming 기법으로 풀이하는 방법을 이야기 해볼 것이다.

먼저 본인은 이 문제에 접근할 때, 역순으로 접근해 주었다. 다시 말해서 , 1일부터 N일 까지 일할 때 벌 수 있는 최대이익을 구한 것이 아니라, 역으로 N일부터 1일까지 일을 한다고 가정했을 때, 벌 수 있는 최대이익을 구해주었다.

왜 ?? 1일부터 할 경우 계산이 너무 복잡해지기 때문이다.

예를 들어서 1일날 일을 하고 1일날 일함으로써 소모되는 날이 x라고 가정했을 때 , 1 + x 날 일했을 때 얻을 수 있는 수익과,  1+ x날 일을 하지 않았을 때 얻을 수 있는 수익 등등... 비교해야 하는 것들과 연산해야 되는 것들이 많아지는 것 같아서 역순으로 계산을 해 주었다.

헷갈리지 말자. 일은 반드시 1일부터 N일까지 해야 하는데 , 우리는 계산만 N일에서 1일로 역순으로 하는 것이다.

하나의 예를 들어보면 N번째 날 일을 함으로써 소모되는 날이 2일인데 , 역순으로 계산한다고 해서, N번째 날 일을하면 N - 1번째 날은 일을 못하고, N - 2번째 날부터 다시 일을 할 수 있다 ! 라고 계산을 하면 안된다는 것이다.

우리는 최대이익만 역순으로 계산할 뿐이지, 시간이 흐르는 것은 1 ~ N일 순으로 흐른다는 것을 헷갈리지 말자.

그럼 문제에 나와있는 예제입력1 번을 통해서 문제를 해결해보자.

[ (3 , 10) , (5 , 20) , (1 , 10) , (1 , 20) , (2 , 15) , (4 , 40) , (2 , 200) ]

이렇게 총 7일동안 일할 때 소모되는 날과 이익이 적혀있다.

위에서도 말했듯이 가장 마지막 날부터 이익을 구해보자.

첫 번째로 7번째 날이다. 일을 할 수 있을까 ?? 할 수 없다. 왜냐하면 , N + 1번째날 바로 퇴사를 해버려야 하는데 , 7번째 날 일을 하게 되면 2일을 소모하게 되는 것이고, 이는 N + 1번째 날 퇴사를 할 수 없게 되기 때문에 일을 할 수가 없다.

따라서 7번째 날 얻을 수 있는 최대이익은 0원이다.

두 번째로 6번째 날을 보자. 이 날 또한 7번째 날과 동일한 이유로 일을 할 수가 없다.

따라서 6번째 날 얻을 수 있는 최대이익은 0원이다.

세 번째로 5번째 날을 보자. 이 날은 처음으로 일을 할 수 있는 날이다. 왜냐하면 일을 하더라도 N + 1번째 날 퇴사가 가능하기 때문이다.

일을 할 수 있다고 해서 반드시 일을 해야하는 것은 아니다. 왜냐하면 일을 하지 않고 그냥 넘어감으로써 더 큰 이익을 얻는 경우도 발생할 수 있기 때문에 일을 반드시 해야 하는 것은 아니다.

그럼 5번째 날 크게 보면 2가지 경우가 존재한다.

1. 일을 하는 Case.

2. 일을 하지 않는 Case.

만약 일을 하게 된다면 얼마의 이익을 얻을 수 있을까 ??

바로, 5일날 일을 함으로써 벌 수 있는 이익 + 7일날 일을 함으로써 벌 수 있는 이익 이 될 것이다.

왜 갑자기 7일이 나왔을까 ?? 5일날 일을 하면 2일을 소모하게 되고 , 가장 빠르게 그 다음 일을 시작할 수 있는 날이 7일이 된다. 따라서 7일날 일을 함으로써 벌 수 있는 이익이 되는 것이다.

이 경우, 벌 수 있는 이익이 5일날 일 함으로써 버는 이익 '15' + 7일날 일 함으로써 버는 이익 '0' = 15 의 이익을 얻게 된다.

두 번째로 일을 하지 않는다면 ???

일을 하지 않는다면 , 6일날 일을 함으로써 벌 수 있는 최대이익이 될 것이다. 왜 ?? 5일날 일을 하지 않으면, 그 다음날인 6일날 바로 일을 할 수 있게 되고, 이 때 얻을 수 있는 최대이익이 5일날 일을 함으로써 얻게되는 최대 이익이 될 것이다.

이 경우에는 6일날 벌 수 있는 최대이익 = '0' 의 이익을 얻게된다.

( 바로 이런 부분 때문에 역순으로 계산을 한 것입니다. 만약 위의 내용을 계산할 때, 7일날과 6일날 일을 함으로써 벌 수 있는

 이익을 몰랐다면 계산이 위의 내용처럼 간단하지만은 않았을 것입니다. )

따라서 5일날 벌 수 있는 최대이익은 15와 0중에 더 큰 값인 15가 된다.

4일날을 보자. 이 경우에도 일을 할 수 있다. 일을 하더라도, N + 1번째 날 퇴사가 가능하기 때문이다.

이 경우에도 2가지 선택권이 생긴다. 일을 하느냐 마느냐 !

일을 하게 될 경우 얻게 되는 최대이익은 "4일날 일을 함으로써 얻게 되는 이익 + 5일날 얻을 수 있는 최대이익" 이 된다.

왜 ?? 4일날 일을 하면 하루를 소모하게 되고, 바로 5일날 부터 새로운 일을 다시 할 수 있기 때문이다.

그럼 이 때 얻을 수 있는 이익은 '4일날 일을 함으로써 얻게되는 이익(20) + 5일날 얻을 수 있는 최대이익(15)' = 35 가 된다.

일을 하지 않을 경우에는 "5일날 얻을 수 있는 최대이익"이 된다. 왜냐하면 일을 하지 않고 넘어가게 되면, 바로 5일날 부터 새 일을 다시 시작할 수 있기 때문에, 이 경우에는 얻을 수 있는 최대이익이 '5일날 일을 함으로써 얻을 수 있는 최대이익' 이 된다.

따라서 '15'가 되는데, 2개의 값을 비교해보면 4일날 얻을 수 있는 최대이익은 '35'가 된다.

그럼 여기서 위의 내용들을 토대로 일반화를 한번 시켜보자.

먼저 본인이 이익을 계산하기 전에 항상 체크해 주었던게 있다. 바로 위에서 분홍색 진한 글씨로 표현된 조건들인데

바로, "해당 날 일을 하게 되면, N + 1번째 날 퇴사가 가능한지?" 이다. 퇴사가 불가능하다면 선택권이 없이 무조건 일을 못하게 된다.

만약 N + 1번째 날 퇴사가 가능하다면 2가지 선택권이 생기게 된다. 일을 하느냐 마느냐 !

지금부터는 하나의 수식으로 표현해보자. F[A] = B !

F[A] = B의 의미는 "A번째 날 일을 함으로써 얻게되는 최대이익은 B입니다." 이다.

그리고 A번째 날 일을 함으로써 , 'Day'만큼의 날짜가 소모되고 , 'Cost'만큼의 이익을 얻을 수 있다고 가정해보자.

그럼 A번째 날 일을 하게 되면 얻을 수 있는 이익은

F[A] = F[A + Day] + Cost 가 된다.

일을 하지 않게 되면 얻을 수 있는 이익은 F[A] = F[A + 1] 이 된다.

2개의 값 중에서 더 큰 값이 F[A]의 값이 되는 것이다.

이 부분을 본인이 구현한 코드는 아래와 같다.

void Solution()
{
    for (int i = N; i >= 1; i--)
    {
        if (i + Day[i] > N + 1) DP[i] = DP[i + 1];
        else DP[i] = Max(DP[i + 1], DP[i + Day[i]] + Cost[i]);
    }
    cout << DP[1] << endl;
}

굳이 코드를 가져온 이유는 설명할 부분이 하나 있어서이다.

먼저 line3)을 보면 처음에 말했듯이, N번째 날부터 1일까지 역순으로 구하기 위해서이다.

line5~6)에 걸려있는 if-else 문이, "N + 1번째 날 퇴사가 가능하냐 아니냐" 를 묻는 조건문이다.

line5) 같은 경우에는 N + 1번째 날 퇴사를 하지 못하는 경우를 line6) 같은 경우에는 N + 1번째 날 퇴사를 할 수 있는 경우를 나타낸 것이다. 그런데 ! line5)에 적힌 조건문에 이상한 점이 하나 있다.

바로, " i + Day[i] > N + 1 " 이라고 적혀있다는 것이다. 왜 " i + Day[i] >= N + 1 "이 아닐까 ??

분명, N + 1번째날 퇴사를 한다고 했는데, 마치 N + 2번째 날 퇴사를 하는 것 처럼 표현해놓은 것일까 ??

이 부분은 이 문제를 코드로 표현하다 보니 저렇게 표현한 것이다.

예를 들어서 N = 7 이고 , 8일날 퇴사를 한다고 가정해보자. 그리고 7일날 일을 함으로써 소모되는 날은 '1일'이라고

가정해보자. 그럼 우리는 7일날 일을 할 수 있을까 없을까?? 일을 할 수 있다. 어차피 하루만 소모하기 때문에 7일날 일을 하고 8일날 퇴사를 하면 된다.

그런데 ! 위의 조건문을 "i + Day[i] >= N + 1" 이라고 설정해놓고 계산을 한다면

"7 + 1 >= 8" 로써 if문에 조건을 만족해서 else로 가지 않고 if문의 내용을 수행하게 된다.

if문의 조건은 "N + 1번째 날 퇴사를 하지 못하는 경우" 에 해당하는 조건문이다.

그런데 ! >= 으로 해버리는 순간, 7일날 일을 할 수 있음에도 불구하고, 8일날 퇴사를 하지 못하는 조건문이 실행되는 상황이 발생하는 것이다.

왜 그러냐면 우리는 머릿속으로는 7일에서 하루 일하면, 8일부터 일이 가능하다 ! 라는 것을 알고 있지만, 코드로 구현할 때

7 + 1 >= 8 이냐고 묻게 되면 그렇다 라고  프로그램은 대답하기 때문이다. 따라서 , 이런 경우를 막아주기 위해서 위와 같이 조건문을 걸어준 것이다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 25
using namespace std;
 
int N, Answer;
int Day[MAX];
int Cost[MAX];
int DP[MAX];
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Day[i] >> Cost[i];
    }
}
 
void Solution()
{
    for (int i = N; i >= 1; i--)
    {
        if (i + Day[i] > N + 1) DP[i] = DP[i + 1];
        else DP[i] = Max(DP[i + 1], DP[i + Day[i]] + Cost[i]);
    }
    cout << DP[1] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}