[BOJ]13302-리조트

[BOJ]13302-리조트

dp테이블의 의미는 dp[a][b]=c라고 했을 때 'a번째 날까지 쿠폰 b개가 존재하기 위해서 필요한 최소 금액 c' 이다. 쿠폰 3개를 하루 이용권으로 교환할 수 있기 때문에 따로 처리를 해주어야 한다. 이는 28~31번째 줄에 나와있다. 처음에는 쿠폰이 3장 이상 모이자마자 사용할 수 있다고 처리해서 틀렸다. 실제로는 3장 이상을 모은 다음 날부터 사용이 가능하다. 예를 들어 [3일권][5일권]을 선택했을 때, 25000+37000-10000으로 계산했다. 왜냐하면 dp배열 상으로는 dp[8][3]이 되므로 마지막 처리에서 dp[8][3]=c -> dp[8][0]=c-10000으로 계산하는 논리였기 때문이다. 실제로는 dp[8][3]=c -> dp[9][0]=c가 되어야 한다.

#include<stdio.h>
#include<algorithm>
using namespace std;
#define INF 1<<29
#define SIZE 111
int dp[SIZE][SIZE];
int main(){
    int n,m;    scanf("%d %d",&n,&m);
 
    int arr[SIZE]={0};
    for(int i=0,tmp ; i<m ; i++){
        scanf("%d",&tmp);
        arr[tmp]=1;
    }
 
    for(int i=0  ; i<=n ; i++)
        for(int j=0 ; j<=n ; j++)
            dp[i][j]=INF;
 
        dp[0][0]=0;
        for(int i=0 ; i<=n ; i++){
            if(arr[i]){
                for(int j=0 ; j<=n ; j++){
                    dp[i][j]=min(dp[i][j],dp[i-1][j]);
                }
            }
 
            for(int j=3 ; j<=i ; j++){
                if(dp[i][j]!=INF)
                    dp[i+1][j-3]=min(dp[i+1][j-3],dp[i][j]);
            }
 
            for(int j=0 ; j<=i ; j++){
                dp[i+1][j]=min(dp[i+1][j],dp[i][j]+10000);
                dp[i+3][j+1]=min(dp[i+3][j+1],dp[i][j]+25000);
                dp[i+5][j+2]=min(dp[i+5][j+2],dp[i][j]+37000);
            }
        }
 
        int ans=INF;
        for(int i=0 ; i<=n ; i++){
            ans=min(ans,dp[n][i]);
        }
 
        printf("%d\n",ans);
        return 0;
    }