[삼성 기출/C++] 14501번 : 퇴사

문제

 

풀이

DP사용. DFS로 푸는 사람도 많았다.

날짜를 1에서 시작하는 것보다 N에서 시작하는게 코드 구현이 더 간단하다.

 

경우

1. 날짜 i에 상담을 진행한 경우 -> dp[i]=dp[i+t[i]]+p[i]

2. 날짜 i에 상담을 진행하지 않은 경우 -> dp[i]=dp[i+1]

 

22번째 line에서 dp[i]=0; 로 작성해서 틀렸었다.

나와있는 테스트케이스는 모두 맞췄는데, 다른 부분에서 조건이 위배됐나 봄.. 

 

 

코드

#include <stdio.h>
#include <iostream>
#include <cstdio>
using namespace std;
 
 
 
int main(){
    int dp[20]={0};
    int n;
    int t[16], p[16];
    
    scanf("%d", &n);
    
    for(int i=1;i<=n;i++){
    
        scanf("%d %d", &t[i], &p[i]);
    }
    
    for(int i=n;i>0;i--){
        if(i+t[i]-1>n) {dp[i]=dp[i+1];}
        else{
            dp[i]=max(dp[i+t[i]]+p[i],dp[i+1]);
        }
            
    }
   
   
           
   printf("%d", dp[1]);
    
}