백준, BOJ, 14501번 C++ [CPP]

난 어려웠다.

생각이 났지만 어떻게 해야할지 몰랐다.

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

14501번: 퇴사

 

---

 

맞는 풀이를 보기 전에 설명부터 해보자.

 

이런 문제는

첫날과 i번째의 날일 때 어떤 상황일까 생각해봐야 한다.

 

첫날은 어떨까??

만약 {5,10} 이고 다음날 {2,30}이 있다면 해야할까 말아야 할까?

즉, 뒤에 뭐가 있냐에 따라 할 것인가 하지 않을 것인가 정해진다는 말이다.

 

그렇다면 i번째가 마지막날이라고 해보자.

i번째의 날은 해야할 까?

i번째 날은 상담이 진행 중이면 당연히 못하고 2일 이상 걸리면 못한다.

 

?????? 

진짜 모르겠다.

다시 생각해보자..

1일차에 상담을 한다면 4일 째 얻는 돈은 10원

-> 4일차에 상담을 한다면 5일 째 얻는 돈은 20원

-> 4일차에 상담을 하지 않는다면 5일 째 얻는 돈은 10원

...

---

1일차에 상담을 안한다면 2일차로 넘어감 2일 째 얻는 돈은 0원

-> 2일차에 상담을 한다면 7일 째에 얻는 돈은 20원

-> 7일차에는 상담을 하면 7일을 넘어버려서 상담을 할 수 없음

 

---

 

2일차에 상담을 안한다면 3일차에 얻는 돈은 0원

-> 3일차에 상담을 한다면 4일 째 얻는 돈은 10원

-> 4일차에 상담을 한다면 5일 째 얻는 돈은 20원

...

 

---

???

4일 째 얻는 돈이 2가지 경우가 나왔다.

1일차 상담한 경우, 1일차 상담하지 않은 경우

즉, 위의 두 경우 중 큰 값을 취해야할 것이다.

 

흠...

그러니까..하나씩 다 뒤져봐야 한다는 얘기다.ㅎㅎ

 

1일차에 상담했으면 4일차 때의 최댓값 + 상담한 값이고.

1일차에 상담 안했으면 2일차 때의 최댓값이 되는 것이다.

즉, 상담했을 때, 안했을 때 값 중 최댓값을 고르면 될 것이다.

 

 

그렇다면 8일에 나갈건데

7일차의 최댓값은..?

7일차에 상담한다면 (7 + 상담날), + 상담한 값

7일차에 상담 안하면 (8일차의 최댓값)

??

여기서는 7일차가 2일이 걸리니까.. 상담을 할 수 없다.

즉, 7일차에 상담을 안하니 8일부터에서의 최댓값을 구하자.

8일은 퇴사니 값이 0이겠다.

 

++더해서

이해하기 쉽게

7일차에 상담이 1일 걸린다면..

7일차에도 상담이 가능하다. 

7일차 최댓값은 8일차 최댓값 + 7일차의 상담한 값이 되겠다.

 

---

 

앞에서부터 결과를 얻어가는 것이 아닌 마지막부터 거꾸로 정해지니까 어려운 것이다.

즉, 마지막 날에 상담을 하느냐 하지 못하느냐부터 시작해서 첫날까지 오게 만들면 된다.

 

이건 많이 풀어보지 않고서야 생각이 나지 않는다.

 

#맞는 풀이

#include<iostream>
#include<algorithm>

using namespace std;

int N;
int dp[16];
int t[16];
int m[16];

//해당 day날의 최댓값
int solve(int day){
    //해당 day가 N+1보다 크다면 퇴사날에도 상담이 끝나지 않았다는 소리다. max에 끼어들지 못하게 임의로 작은 값을 준다.
    if(day > N+1) return -1000000;
    //해당 day가  N+1이면 퇴사날이기 때문에 0의 값을 준다.
    if(day == N+1) return 0;
    
    //dp[day]의 값이 있다면 바로 return.
    int ret = dp[day];
    if(ret != -1) return ret;
    
    //없다면 재귀형식으로 solve (1) -> solve(2), solve(4) + 10 이런식으로 찾아간다.
    ret = max(solve(day + 1), solve(day + t[day]) + m[day]);
    return ret;
}


int main(){
    cin >> N;
    //초기화
    for(int i = 1; i<=N; i++){
        int a, b;
        cin >>a >> b;
        t[i] = a;
        m[i] = b;
        dp[i] = -1;
    }
    
    int ret = solve(1);
    cout << ret << "\n";
}