[BOJ] 14501번 : 퇴사 (C++)

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

14501번: 퇴사

 

dp 문제이다. 

상담일 수는 t배열에 저장해주었고, 상담액은 p배열에 저장해주었다. 추가로 1-indexed로 풀어주었다. 

처음엔 for문을 앞에서부터 돌리려고 하였는데, 그 대신 뒤 원소부터 돌면서 dp값을 구해주면 된다. 

우선, 현재 일 수(i)에다가 일이 걸리는 기간(t[i])을 더했을 때 내가 근무하는 날짜를 넘어가게 되면 i번째 날에 일할 수 없다. 

그래서 위의 값을 기준으로 현재 일 수에 일을 할 수 있거나 / 없거나 이다. 

현재 날짜에 일을 할 수 없다면, i번째 일을 안하고 넘어갈 것이다. i번째 날을 스무스하게 통과하고 날짜를 한 칸 넘기면 된다.

현재 날짜에 일을 할 수 있다면, i번째 일을 했을 경우와 하지 않을 경우 중 더 큰 경우를 선택해줘야 한다.

둘을 비교해주는 식은 d[i] = max(d[i+t[i]]+p[i], d[i+1]) 를 해주면 된다.

i번째 날에 상담을 했다는 것은 이번 상담이 끝나면 바로 i+t[i]번째 날로 가게 되는 것이고, 나를 거쳐서 갔으니 p[i]값에다가 다음 번에 상담이 가능한 d[i+t[i]]를 더해주는 것이다.

상담을 하지 않았다는 것은 그냥 바로 다음 날로 넘어가는 것이라, 나를 거쳐가지 않은 것이니 나를 더해주지 않고 d[i+1]과 같게 되는 것이다. 

그래서 위와 같은 식이 나오게 된 것이다. 

 

d[7] = d[8] = 0

d[6] = d[7] = 0

d[5] = max(d[7]+15, d[6]) = 15

d[4] = max(d[5]+20, d[5]) = 35

d[3] = max(d[4]+10, d[4]) = 45

d[2] = max(d[7]+20, d[3]) = 45

d[1] = max(d[4]+10, d[2]) = 45

 

추가로 현재 N의 범위가 N (1 ≤ N ≤ 15) 으로 매우 작기 때문에 완전탐색으로 풀 수도 있다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int d[20]; //d[i]=k : i번째 일에 상담을 시작했을 때 얻을 수 있는 최대 수익
int t[20]; //상담일 수
int p[20]; //상담액

int main(){
    int n; cin>>n;

    for(int i=1; i<=n; i++){
        cin>>t[i]>>p[i];
    }

    for(int i=n; i>=1; i--){
        //i번째 일에 상담을 할 수 있는 경우
        if(i+t[i]-1<=n){
            //상담을 할 때와 안할 때를 비교하여 큰 값을 넣어줌
            d[i] = max(d[i+t[i]]+p[i], d[i+1]);
        }
        //i번째 일에 상담을 할 수 없는 경우
        else d[i]=d[i+1];
    }
    cout<<*max_element(d+1, d+n+1); //1-indexed이므로!!
}

 

회고)

왜 i번째를 상담하지 않으면 d[i]=d[i+1] 인지가 너무 이해가 안됐다. 

그리고 문제 풀이 자체가 원래의 dp방식이랑은 약간 달라서 이해가 잘 가지 않았다. 

i번째를 상담할 수 있으면 i번째 상담을 거쳐가서 p[i]값과 그 바로 다음 d[i+t[i]]을 더해주면 되고,

i번째를 상담할 수 없다면 i번째 상담을 거치지 않으니 p[i]값을 더해줄 수 없고 그냥 바로 다음 날로 넘어가게 되는 것이다..

이 문제에 3시간은 넘게 쏟은 듯..

 

추가로 이해할 때 도움이 된 유튜브 강의 해설 영상이다. 

https://www.youtube.com/watch?v=VEbh7lCu7Ic