[백준] 15486번: 퇴사 2 (C++)

위의 문제에 포함되어 있는 예시로 설명한다

 

처음에는 for문을 두 개를 작성한 후

탐색하는 날짜에 필요한 상담 일 수 만큼

sum 변수를 추가로 설정하여 합하는 식으로 작성했다

물론 그렇게도 풀릴 것 같았지만

예외 처리가 많이 필요했다

 

그래서 다른 방법을 찾았다

내가 문제를 보고 답을 직접 구할 때도

뒤에서부터 구했던 것 같다

막상 코드로 작성하니 머리 속으로 풀었던 것 그대로 녹여내면 되는데 

아직까지 쉽지 않은 듯하다

 

뒤에서 부터 역순으로 찾는다

날짜가 넘어가면 그 전 인덱스를 탐색하고

dp에 저장한다

이후 기존의 dp와 이전 날의 새로운 값을 더했을 때를 비교하여

더 큰 값을 dp에 저장한다 

이후 dp를 모두 구했을 때 나오는 dp[1]을 출력한다

 

// baekjoon 15486

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

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}

#define MAX 1500001

int T[MAX];
int P[MAX];
int dp[MAX];

int main(){
    init();
    
    int N;
    cin >> N;
    
    
    
    for(int i = 1; i <= N; i++){
        cin >> T[i] >> P[i];
    }
    
    dp[0] = 0;
    
    for(int i = N; i >= 1; i--){
        if(i + T[i] > N + 1){
            dp[i] = dp[i + 1];
        }
        else{
            dp[i] = max(dp[i + 1], P[i] + dp[i + T[i]]);
        }
    }
    
    cout << dp[1];
    
    return 0;
}

참고사이트

[백준알고리즘] 15486번 퇴사2 :: 지무룩의코딩일상 (tistory.com)