퇴사

문제: 퇴사 (백준 14501)

구조 분석

최근에 계속 시뮬레이션/구현 문제만 풀다가 간단한 형태의 문제를 봐서 신났다. 그런데 처음에 문제를 봤을 때 어? 스케줄링? 그러면 전형적인 greedy 문제구나! 해서 풀었다가 막혀서 당황했다. 해당 문제는 최대한 많은 스케줄을 잡는 것이 아니라 적당한 스케줄을 했을 때, 얻을 수 있는 최대 수익을 구하는 문제였다. 즉, 이전에 풀었던 계단 오르기 문제와 동일하게 dynamic programming을 이용했어야 한다.

해당 문제의 경우 스케줄은 그저 제약조건과 문제를 위한 함정이었고 본질은 dynamic programming인 것을 알아야 했다.

풀이 방법

우선 dynamic programming을 이용하기 위해서는 각 날짜별 모은 페이의 최대값을 저장하는 배열을 생성해야 한다.

int res[16] = {0,};

그리고 정해야 하는 것이 해당 배열을 오름차순으로 채울 것인지 내림차순으로 채울 것인지 확인해야 한다. 해당 문제의 경우 1계단 또는 2계단씩 오르는 계단문제와는 달리 각 날짜별 상담일수가 제각각이다. 따라서 이러한 경우는 내림차순으로 채우는 것이 맞다.

for (int i=n-1; i>=0; i--) {

}

다음으로는 deadline을 넘는 경우 처리를 해줘야 한다.

int deadline;
for (int i=n-1; i>=0; i--) {
    deadline = T[i] + i;
    if (deadline > n) {
        res[i] = res[i+1];
    }
    else {

    }
}

위의 코드에서 deadline이 n보다 큰 경우 상담이 불가한 경우이므로 해당 날짜의 페이는 뒷 날짜의 페이를 그대로 가져온다.

마지막으로 상담이 가능한 경우 상담을 할지 말지 결정해주면 된다. 상담을 하는 경우에는 res[deadline]의 값을 가져와 상담수당을 더해주고, 상담을 안하는 경우에는 뒷 날짜의 페이를 그대로 가져오면 된다. 둘 중 더 페이가 쎈 경우를 선택하면 된다.

코드

#include <stdio.h>
#include <iostream>
#define MAX(a,b) (a>b?a:b)
using namespace std;

int n;
int T[15] = {0,};
int P[15] = {0,};
int res[16] = {0,};

int main() {
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> T[i] >> P[i];
    }
    int deadline;
    for (int i=n-1; i>=0; i--) {
        deadline = T[i] + i;
        if (deadline > n) {
            res[i] = res[i+1];
        }
        else {
            res[i] = MAX(res[i+1], res[deadline] + P[i]);
        }
    }
    cout << res[0] << "\n";
    return 0;
}

정리

해당 문제는 알고보면 쉬운 문제였는데, 구조분석도 잘 못하고 괜히 조건 따지면서 구현하다가 어렵게 돌아가서 아쉽다.