[C/C++ 백준 14501번] 퇴사 (Silver 4)

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

14501번: 퇴사

딱 보니 예전에 봤었던 계단 오르는 문제(https://bluebluediary.tistory.com/4)랑 거의 같은 문제이다. 다만 오를 수 있는 계단의 수가 정해져 있다는 정도?

 

문제에서 6, 7일의 경우는 아예 불가능하다는 것을 인지하자. 이런 경우 dp에 -1을 저장했다. 나머지 점화식은 계단때와 비슷하다. 

 처음 검사했을 때 틀렸었는데, 모든 날 상담이 불가능한 케이스가 있는 듯하다. ans의 초기값을 0으로 잡아야 하는 이유이다. 그냥 전체적으로 계단 문제와 비슷하다.

---

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	int N;
	scanf("%d",&N);
	int Ti[16], Pi[16], dp[16]={}, ans=0;//dp[i]:i번째 날 상담했을때 얻는 가장 높은 금액 
	for(int i=1; i<=N; i++){
		scanf(" %d %d",&Ti[i], &Pi[i]);
	}
	for(int j=N; j>=1; j--){
		dp[j]=Pi[j];
		for(int k=j+Ti[j]; k<=N; k++){
			dp[j]=max(dp[j], Pi[j]+dp[k]);//가장 큰 dp저장 
		}
		if(j+Ti[j]-1>N)//예제의 6, 7일 같은 케이스 
			dp[j]=-1;
		ans=max(ans, dp[j]);
	}
	printf("%d",ans);
}

---