백준 14501번 C++ 풀이

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

14501번: 퇴사

시간 제한	메모리 제한	solved.ac 티어
2초	512MB	실버 3

문제

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

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

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

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

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

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	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이다.

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

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

---

1일차부터 시작하여 i일에 상담을 진행했을 경우, 받을 수 있는 금액의 최대값을 구하면 된다. 

 

설명에 나온 예제(예제 1)로 알아보자.

 

초기상황은 다음과 같다. 이때 dp는 i일에 받을 수 있는 금액의 최댓값을 기록한 배열이다. 또한 최대로 얻을 수 있는 금액을 max라고 해보자. max의 초기값은 0이다. max는 dp[i]와 순차적으로 비교할 것이다.

 

일	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200
dp	0	0	0	0	0	0	0

 

1일부터 7일까지 순차적으로 따져보자. 1일에 잡힌 상담을 진행한다고 가정해보자. 1일에 상담을 진행했기 때문에 1~3일은 어떠한 상담도 할 수 없다. 또한, 이 경우 4(1 + T1)일째에는 P1인 10만큼을 얻은 상태일 것이다. max = dp[1] = 0이기 때문에 max는 수정하지 않는다.

 

일	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200
dp	0	0	0	10	0	0	0

 

이제 2일차를 따져보자. T2는 5이기 때문에, 2 ~ 6일차동안 상담을 진행할 것이다. 또한 7일의 상담은 2일을 소모해야 하기 때문에 7일차의 상담은 진행할 수 없다. 그렇기 때문에 2일차의 상담을 진행하면 다음과 같아진다. max = dp[2] = 0이기 때문에 역시 max는 수정하지 않는다.

 

 

일	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200
dp	0	0	0	10	0	0	20

 

3일차를 보자. T3은 1이기 때문에 당일에만 상담을 진행할 것이다. 그렇기에 3 + T3인 4일차에 10만큼 얻는다. 1일차에 상담을 진행하던 3일차에 상담을 진행하던, 10만큼을 얻을 수 있다. 명심하자. 우리는 최댓값이 궁금한 것이지, 언제 상담을 진행하는지는 궁금하지 않은 것이다. 따라서 3일차의 상황은 2일차에 진행한 상황과 같다. 역시 max는 0.

 

일	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200
dp	0	0	0	10	0	0	20

 

4일차이다. 이때는 10만큼의 금액을 번 상태이다. 또한 T4역시 1이기 때문에 당일만 상담을 진행한다. 따라서 4 + T4인 5일차에는 dp[4]인 10과 P4인 20의 합인 30을 얻은 상태일 것이다. dp[4]가 max(0)보다 크기 때문에 max는 10이 된다.

 

일	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200
dp	0	0	0	10	30	0	20

 

5일차를 보자. 5 + T5인 7일에는 dp[5] + P5인 45만큼 얻을 수 있다. 기존에 7일에 얻을 수 있는 20보다 크기 때문에, 7일에 얻을 수 있는 금액을 45로 수정한다. 또한 dp[5]가 max(10)보다 크기 때문에 30이 된다.

 

일	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200
dp	0	0	0	10	30	0	45

 

6일차를 보자. 언뜻 보면 6일차에는 다다를 수 없어 6일차에는 받을 수 있는 돈이 없어보이지만, 5일차의 상담을 진행하지 않고, 하루를 쉰 후에 6일차가 되었다면, 6일에는 max인 30만큼 얻을 수 있을 것이다. 이것을 알아야 예제 4번이 통과가 된다. 또한, T6은 4이기 때문에 상담을 진행할 수 없다.

 

일	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200
dp	0	0	0	10	30	30	45

 

7일차도 이전에 말했듯이 상담을 할 수 없다. P7은 45이고 max는 30이기 때문에 max를 45로 수정한다.

 

처음부터 끝까지 돌면서, 얻을 수 있는 금액의 최댓값이 45라는 것을 알았다. 이를 출력하면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int N;
int* T; // Ti
int* P; // Pi
int* dp; // dp 식

void input(){
    cin >> N;
    T = new int[N + 1];
    P = new int[N + 1];
    dp = new int[N + 1];
    fill(dp, dp + N + 1, 0); // 초기화
    for(int i = 0; i < N; i++) {
        cin >> T[i] >> P[i];
    }
}

void solution(){
    int max_pay = 0; // 최댓값을 저장하는 변수
    for(int i = 0; i <= N; i++) {
        dp[i] = max(max_pay, dp[i]);
        // 잘못된 메모리 참조를 하지 않기 위한 조건
        if (T[i] + i <= N) {
            dp[T[i] + i] = max(dp[T[i] + i], P[i] + dp[i]);
        }
        max_pay = max(max_pay, dp[i]);
    }
    cout << max_pay;
}
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    input();
    solution();
}

 

----------------------------------------------- 추가: 22.03.19 A.M. 1:30 -----------------------------------------------

 

또한 dfs의 방식으로도 풀어봤다.

 

함수로 받은 시작날짜로부터 끝날짜까지 반복하면서 탐색한다. 그 과정에서 나온 최대 금액을 저장한다. 반복문을 돌면서 재귀하는데, 이 반복문이 시작날짜부터 끝날짜로 되어있기 때문에, 위에서 말한 것처럼 하루를 건너뛰는 것도 이 과정에서 자연스럽게 구현된다.

 

#include <bits/stdc++.h>
using namespace std;

int N;
int* T; // Ti
int* P; // Pi
int max_pay = 0;

void input(){
    cin >> N;
    T = new int[N + 1];
    P = new int[N + 1];
    for(int i = 0; i < N; i++) {
        cin >> T[i] >> P[i];
    }
}

void solution(int x, int sum){
    if (x > N) return;

    max_pay = max(max_pay, sum);
    for(int i = x; i < N; i++) {
        solution(T[i] + i, sum + P[i]);
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    input();
    solution(0, 0);
    cout << max_pay;
}