백준 문제 14501번 퇴사 문제풀이 c++

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

14501번: 퇴사

 

문제해석

 

문제를 보면 dp 문제임을 어렵지 않게 알 수있는데

나는 탑다운 형식으로 dp를 작성하였다.

예시와 같은 문제일때 1일 부터 확인하는게 아닌 7일부터 확인해야한다.

 

1일을 확인해보자

1일 상담을 하면 2일 3일은 상담을 할 수 없다.

즉 1일 상담의 금액 P[0]과

4일부터 상담했을때 최대 이익 =dp[3]

5일부터 상담했을때 최대 이익 =dp[4]

6일부터 상담했을때 최대 이익 =dp[5]

7일부터 상담했을때 최대 이익 =dp[6]

의 합중 가장 큰것이 답이 된다.

즉 dp[0]=max(p[0]+dp[4],p[0]+dp[5],p[0]+dp[6],p[0]+dp[7])

 

이것을 일반화 하여 작성하면 아래 코드와 같다.

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int T[15];
int P[15];
int dp[15];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n; cin>>n;
    int ans=0;
    for(int i=0; i<n; i++)
    {
        cin>>T[i]>>P[i];
    }
    for(int i=n-1; i>=0; i--)
    {
        for(int j=i+T[i]; j<=n; j++)
        {
            dp[i]=max(dp[i],P[i]+dp[j]);
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans;
}