[C++][백준 14501] 퇴사

[문제]

14501번: 퇴사 (acmicpc.net)

14501번: 퇴사

[문제 풀이]

맨 처음에는 DP 인것은 알고 있었지만 도중에 n일차의 작업이 끝나면 도중에 띄어지는 부분을 어떻게 처리해야 하냐 고민을 많이 했는데 어렵게 고민을 할 필요가 없는 부분이었다.

DP의 특성상 이전에 했던 작업이 이후에 영향을 주니 1일차 2일차 3일차 모든 작업을 고민하는게 아닌 1일차 1일차를 겪은 2일차 1일차, 2일차를 겪은 3일차... 이런 식으로 고민을 하면 되는 문제였다.

쉽게 설명을 하자면 3번째와 2번째는 1번째를 겪고 난 뒤의 값이니 4번째값이 3번째만 합쳐지더라도 1번째와 2번째가 합쳐진 값이니 n과 m사이만 고민을 하면 된다.

 

    for(int i = 1;i<=n;i++){
        cin>>company[i].first>>company[i].second;
        for(int j = 0;j<i;j++){
            if(company[j].first + j <= i and i + company[i].first <= n + 1 ){
                    DP[i] = max(DP[i] , DP[j] + company[i].second);
                    answer = max(answer , DP[i]);
            }
        }
    }

i를 1부터 n까지 가고 해당 날짜와 해당 값을 저장하자.

i이전까지 j를 모두 돌려볼때 j번째 날짜와(해당 날짜로부터 더해지는 날) j날(해당 날짜) 를 더한 값이 i보다 이하이며 i번째 날짜와 i번쨰 날짜부터 걸리는 시간이 범위 안이라면

i번째 날짜의 DP값은 해당 DP의 값과 j번째 날짜의 DP와 현재 날짜의 값을 더한값중에 더 큰 값이다.

answer는 모든 DP중에 가장 큰 값이다.

[코드]

#include<iostream>
#include<vector>
#include<algorithm>

#define endl "\n"

using namespace std;

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

    vector<pair<int, int> > company(n);
    int DP[16] = {0,};

    int answer = 0;

    for(int i = 1;i<=n;i++){
        cin>>company[i].first>>company[i].second;
        for(int j = 0;j<i;j++){
            if(company[j].first + j <= i and i + company[i].first <= n + 1 ){
                    DP[i] = max(DP[i] , DP[j] + company[i].second);
                    answer = max(answer , DP[i]);
            }
        }
    }

    cout<<answer<<endl;

    return 0;
}