[BOJ14501 C++] 퇴사

문제 링크
실버3 짜리 문제 ..!

내가 뭐 어떤 방법으로 풀었는지는 알고리즘 공부를 안해서 모르겠다. DP인가?

알고리즘 수업시간에 엄청 많이 봤던 문제같은데 ..

재귀함수 이용해서 풀어봤다. 재귀함수 단점이 디버깅이 참 어렵단 말이지

짧은건 그래도 보겠는데 거의 상상력으로 만드는 수준

사실 포맷이 정해져 있는 느낌이라 ..

문제는 주어진 행렬 2개로 어떻게 점프해야 가장 점수를 많이 따면서 끝낼까 이런건데

알고리즘(이라할 것도 없음)
처음꺼를 무조건 밟아야 하는 것도 아니고, 스킵해야 되는 경우도 있고,

그 뒤에 꺼도 밟아야하는지 넘어가야하는지 결국 다 해보는 수밖에.

중요했던 건 idx랑 i를 구별지어서 썼다는거

i는 모든 경우를 볼 때 쓰는 값이었고,

idx는 i로부터 점프점프! 하는 친구.

for문을 0~N 까지 돌면서 일할 수 있으면

• value를 일한 값만큼 추가
• Time index도 일한 시간만큼 추가

그리고 가지를 치기 시작.. recursive하게 ..

다음 밟는 곳에서도 일할 수 있으면 .. 없으면 ..

그리고 뒤로 쓰르륵 돌아오면서 모든 경우를 다 더해서 결과 값 value가 나올텐데,

그게 max면 update도 해주고 최종적으로 return도 해주고.

그러다보면 나중엔 모든 경우 중에 최고가 나오겠지

사실 이게 N 값이 적어서 가능하지, N이 컸으면.. 근데 다 안보고 어떻게 알아!

오랜만에 재귀함수 짜보고 재밌었다. 더 좋게 풀면 좋을텐데

//
// Created by 신성준 on 2023/02/26.
//
#include <iostream>
using namespace std;

int dp(int *T, int *P, int idx, int N){
    if(idx > N) { //N+1을 넘어갔다
        return 0;
    }
    int max_value = 0;
    for(int i = idx; i < N; i++){
        int value;
        if((i + T[i]) <= N){ //마지막 하루도 열심히 일할 수 있잖아!
            value = P[i];
            idx = i + T[i];
        }
        else{ //지금 일은 못맡고 다음 일은 되려나?
            value = 0;
            idx = i + 1;
        }
        value += dp(T, P, idx, N);

        if(value > max_value){
            max_value = value;
        }
    }
    return max_value;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    int *T = new int[N];
    int *P = new int[N];

    for(int i = 0; i < N; i++){
        int t, p;
        cin >> t >> p;
        T[i] = t;
        P[i] = p;
    }

    int value = dp(T, P, 0, N);
    cout << value;

}