백준 14501 퇴사 C++

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

14501번: 퇴사

 

최종 코드

• GitHub https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ14501_dfs.cpp

hwayeon351/BEAKJOON-Algorithms

//
//  main.cpp
//  BJ14501
//
//  Created by Hwayeon on 2020/12/10.
//
#include <iostream>
using namespace std;

int N;
int T[15];
int P[15];
int money = 0;

void consult(int i, int pay, int day){
    if(i >= N){
        if(pay > money) money = pay;
        return;
    }
    if((day+T[i]<=N) && (i+1+T[i]<=N+1)) consult(T[i]+i, pay+P[i], day+T[i]);
    consult(i+1, pay, day);
    return;
}

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=0; i<N; i++) cin >> T[i] >> P[i];
    consult(0, 0, 0);
    cout << money << endl;
    return 0;
}

 

• GitHub https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ14501_dp.cpp

hwayeon351/BEAKJOON-Algorithms

//
//  main.cpp
//  BJ14501_dp
//
//  Created by Hwayeon on 2021/07/05.
//

#include <iostream>
using namespace std;
int N;
int T[15], P[15], dp[15];
int money = 0;

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=N-1; i>=0; i--){
        cin >> T[i] >> P[i];
        if(T[i]+(N-i-1) > N){
            T[i] = 0;
            P[i] = 0;
        }
    }
    dp[0]  = P[0];
    money = dp[0];
    for(int i=1; i<N; i++){
        int after_consult = dp[i-T[i]] + P[i];
        if(after_consult > dp[i-1]) dp[i] = after_consult;
        else dp[i] = dp[i-1];
        if(dp[i] > money) money = dp[i];
    }
    cout << money << endl;
    
    return 0;
}

---

풀이 과정

• DFS 알고리즘 풀이

N일 이내에 할 수 있는 상담의 경우의 수를 구하고 최대 비용인 경우 답을 갱신해 나가는 방식으로 DFS를 적용하여 풀었다.

아래 과정을 반복하며 i번째 상담을 진행하는 경우와 진행하지 않는 경우, 두 가지로 나뉘어 재귀 호출을 하였다.

 

1. i가 N보다 크면, pay > money이면 money = pay를 해주고 재귀를 종료시킨다.

 i는 0부터 시작하기 때문에 i > N인 경우는 이미 상담일이 N일 초과되었음을 의미한다. 따라서 재귀를 종료한다.

2. 만약, 현재 상담을 할 수 있으면, consult(i+T[i], pay+P[i], day+T[i])로 재귀를 호출한다.

 현재 상담을 하려면 다음 두 조건을 만족해야한다.

1. day+T[i] <= N -> 이전에 진행한 상담일 수와 현재 상담에 소요되는 일 수가 N보다 작거나 같아야 한다.
2. i+1+T[i] <= N+1 -> 현재 일 수(i+1)와 현재 상담에 소요되는 일 수의 합이 N+1보다 작거나 같아야 한다. N+1과 비교하는 이유는 i = 7, T[i] = 1이고 N=7인 경우 해당 날짜에 상담이 이뤄질 수 있기 때문에 N+1을 기준으로 삼는다.

 

• DP 알고리즘 풀이

상담일의 역순으로 최대값을 찾아나가는 방식으로 문제를 풀 수 있다.

1. 입력 T, P를 역순으로 배열 T, P에 저장한다. 이때, T+(N-i-1)이 N보다 큰 경우는 애초에 상담을 진행할 수 없기 때문에 T[i] = P[i] = 0으로 바꿔준다.

2. dp[0] = P[0], money = dp[0]으로 초기화한다. 즉, 마지막 상담 비용이 dp[0]의 초기값이 된다.

3. 1부터 N-1 인덱스까지 다음 과정을 반복한다.

1. 현재 상담이 이뤄지는 경우, 최대 수익을 구한다. 현재 상담이 이뤄지기 때문에 현재 i에서 상담 소요 시간 T[i]을 빼줘야 한다. 그러면 현재 상담이 이뤄진 이후의 최대 수익이 dp[i-T[i]]이다. 여기에 현재 상담의 페이 P[i]를 더한다. after_consult = dp[i-T[i]] + P[i]
2. 만약, after_consult가 하루 뒤에 진행할 상담의 최대 수익 dp[i-1] 보다 큰 경우, 현재 상담을 진행해야 하므로 dp[i] = after_consult가 된다.
3. 하루 뒤에 진행할 상담의 최대 수익 dp[i-1]이 after_consult보다 큰 경우는 현재 상담을 진행하지 않는 것이 최대 수익을 만들 수 있기 때문에 dp[i] = dp[i-1]을 한다.
4. dp[i]가 최대 수익인 경우, money = dp[i]를 한다.