[백준] 퇴사

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

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e17;
int n,t[16],p[16];
int DT[16];
int main(){ IOS;
	cin>>n; for(int i=1;i<=n;i++) cin>>t[i]>>p[i];
    for(int i=n;i>=1;i--){
        if(i+t[i]-1<=n)
            DT[i]=max(DT[i+1],DT[i+t[i]]+p[i]);
        else
            DT[i]=DT[i+1];
    }
    cout<<DT[1];
}

 

나는 이 '역방향' 채우기 아이디어를 어떻게 떠올렸는가?

 

특정 날짜에 상담을 시작했을 때부터 t일 동안 일을 하지 못하므로 t일 후에야 다른 일을 시작할 수 있다. 이를 동적 계획법적으로 생각해보면 index가 클 경우의 부분문제가 index가 작을 때의 부분문제보다 먼저 등장하므로, for문을 거꾸로 돌린다는 아이디어를 떠올렸다.

 

다른 상황은 N일이 넘어가는 순간 일을 하지 못한다는 것이다. 그래서 N일부터 시작한다면 고려할 것이 없겠다는 생각도 했다.