[백준] 14501: 퇴사 (with C++)(2가지 방법)

처음 봤을 때, 음 이건 뒤에서부터 DP구만, 하면서 점화식을 세웠다. 그런데 세우다 보니 '이 날 일 할까 말까'문제여서, 재귀로 풀 수도 있을 것 같았다. 게다가 N이 그렇게 크지도 않아서 그냥 재귀로 풀어야겠다~ 하고 재귀로 풀었다. DP가 어려운 문제는 아니었는데 어쨌든 재귀가 더 쉬우니까 ㅋㅋㅋ 귀차니즘... 아니 이건 진짜 재귀로 푸는거랑 DP로 푸는거랑 시간차이가 얼마 안날텐데? 뎁스초과가 날 만한 문제도 아닌데? 그럼 재귀로 풀어야지! 의 사고과정.

 사실 그래도 DP로 풀어야 한다. N이 작아서 그렇지 재귀로 풀면 중복계산이 꽤 나오는 구조이다. 오늘 일 하고/안하고 + 뒷날 최대 여기서 똑같은 뒷날 최대를 매번 계산해야 하는 거다. N이 <=100이고 매일매일 하루만 걸리는 작업이 나온다고 생각해 보면 시간 차이가 꽤 날 것 같다. 그래서인지 DP로 푼 사람들이 훨씬 많다. 아무튼 이런 이유들로 인해, DP로도 풀어 주는 게 인지상정... 으로 이번 포스팅에서는 두 개의 풀이법을 소개하려고 한다.

 

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

3	5	1	1	2	4	2
10	20	10	20	15	40	200

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/14501

14501번: 퇴사

그래요. 첫번째 풀이

재귀

기본적으로

1. 가능한 모든 경우를 탐색해야 한다.

2. 각 날에 일을 할 수도 있고, 하지 않을 수도 있다.

3. 각 날짜에 대해 이 날짜에 일하는 경우와, 포함하지 않고 일하는 경우를 계산해서 더 큰 값을 저장하면 된다.

 

#include<iostream>

using namespace std;
int* payment;
int* day;
int N;

int max_payment(int day_now, int pay_now) {
    if(day_now == N){
        return pay_now;
    }
    else if(day_now > N) {
        return -1;
    }
    int days = day[day_now];
    int pay = payment[day_now];
    //do this appointment
    int a = max_payment(day_now + days, pay_now + pay);
    //skip this appointment
    int b = max_payment(day_now + 1, pay_now);

    return max(a, b);
}


int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;
    payment = new int[N];
    day = new int[N];

    for(int i=0; i<N; i++) {
        cin >> day[i] >> payment[i];
    }

    cout << max_payment(0, 0) << "\n";
	return 0;
}

변수명이 엉망입니다. 간단하다. 자 두번째 풀이.

 

DP

1. 점화식

DP는 점화식이 생명이니까 일단 점화식부터 세우자.

d[i] = ith날부터 얻을 수 있는 최대 수익

p_i = ith날의 일에 대한 수익

t_i = ith날의 일이 걸리는 시간

이라고 하자. 그럼 d[i]는

 

d[i] = max(d[i+1], p_i + d[i+t_i])

 

이 점화식이 왜 나오냐 하면,

1. d[i](i번째 날부터 얻을 수 있는 최대 수익)는 i번째 날에 일을 하는 경우와 안하는 경우에 각각 얻을 수 있는 수익의 최대이다.

2. 그럼 대충 점화식 형식이 d[i] = max(i번째 날 일했을 때 얻는 전체 수익, i번째 날 일 하지 않았을 때 얻는 전체 수익) 일 것이다.

3. i번째 날 일했을 때 얻는 전체 수익은, p_i + d[i+t_i]이다. 왜냐하면 i번째 날 일을 하면 i+t_i번째 날 까지는 일을 못하니까.

4. i번째 날 일 하지 않았을 때 얻는 전체 수익은 d[i+1]이다. 이것은 d[]의 정의에서 자명하다.

5. 따라서 점화식은 d[i] = max(d[i+1], p_i + d[i+t_i])

2. d 배열 초기 상태

뒤에서부터니까 d[]의 마지막 원소만 초기화해주면 된다. 이것은 마지막 날 payment이다. 이렇게 해두고 마지막 날의 전날부터 d를 업데이트한다. 꼭 이렇게 안해도 되고 마지막 날부터 d를 업데이트하되 마지막 날 +1 을 0으로 해줘도 된다.

 

3. 주의사항

1) 일을 할 수 없는 날

 단, 일을 할 수 없는 날이 있을 수 있다. 예를 들어 위 예시에서 6일과 7일은 일을 할 수가 없다. 이런 경우는 p_i를 0으로 둬야 한다. 따라서 payment를 저장할 때 들어오는대로 다 저장하지 말고 일을 할 수 없는 날이면 0을 저장해 준다.

 

* d 배열 마지막 원소가 나타내는 날에 걸리는 시간이 1을 넘으면, 예를 들어 7일이 마지막 날인데 7일에 걸리는 시간이 1을 넘었으니까 7번째 날의 payment로 d를 초기화하면 안되는거 아닌가?

- 그래서 payment를 저장할 때 애초에 0을 넣어준다는 거고, 0이 들어가 있을 수도 있는, 이미 전처리된 payment로 d를 초기화 하는 것이다.

 

2) i+t_i의 값이 d배열 길이를 초과할 수 있다. 이 경우는 조건을 붙여서 걸러주도록(이 경우 d[i] = max(d[i+1], p_i)) 하자.

 

* 이런거 다 필요 없고 그냥 d를 엄청 길게 해서, 뒤를 다 0으로 초기화해놓으면 되지 않나?

- 내가 낭비되는 공간이 명시되어 있는걸 좀 싫어한다. 난 그게 더 귀찮은거 같다. 죄송합니다. 이렇게 해도 될 것 같음.

 

그럼 다음과 같이 코드를 짜면 된다.

#include<iostream>

using namespace std;

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int* payment;
    int* day;
    int N;
    int* d;
    cin >> N;
    payment = new int[N];
    day = new int[N];
    d = new int[N];

    for(int i=0; i<N; i++) {
        cin >> day[i] >> payment[i];
        if(day[i] + i > N) {
            payment[i] = 0;
        }
    }

    d[N-1] = payment[N-1]; //initialize d[last day] 
    for(int i=N-2; i>=0; i--) { //from (last day-1),
        if(day[i] + i > N-1) {
            d[i] = max(d[i+1], payment[i]);
        }
        else {
            d[i] = max(d[i+1], payment[i] + d[i+day[i]]);
        }
    }

    cout << d[0] << "\n";
	return 0;
}

 

dp가 더 깔끔한 것 같기도 하다.

시간은 별로 차이가 안났던 거 같다.