백준 13302 리조트

출처: https://www.acmicpc.net/problem/13302

이 문제는 dp배열을 방학 날과 쿠폰 개수에 대해 잡아서 풀었다. 

dp[n번째 날][현재 보유한 쿠폰 수 k]=min(dp[n-1][k]+10000원, dp[n-2][k-1]+25000원, dp[n-3][k-2]+37000원, dp[n-1][k-3]) 

dp[n-1][k-3]은 쿠폰 3개 써서 가는 경우를 말한다. 

여기다가 예외 처리 해주면 된다. 

그런데 배열을 너무 작게 잡아서 틀렸습니다가 많이 떴다. 쿠폰 index를 50은 잡아야 된다!!

 

#include <iostream>
#include <stdio.h>
using namespace std;
int n,m,k,ct=1;
int dp[105][50];
bool vac[105];
int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) vac[i]=true;
    for(int i=0; i<m; i++)
    {
        cin >> k;
        vac[k]=false;
        if(ct==k)ct++;
    }
    ct--;
    n-=ct;
    if(ct!=0) for(int i=1;i<=n;i++) vac[i]=vac[i+ct];
    int ma=(n/5)*2+5;
    dp[1][0]=10;
    for(int i=2; i<=n; i++)
    {
        if(!vac[i])
        {
            for(int j=0; j<ma; j++)
                if(i>0) dp[i][j]=dp[i-1][j];
        }
        if(i-1>0)
        {
            for(int j=0; j<ma; j++)
            {
                if(dp[i-1][j]!=0)
                {
                    if(dp[i][j]==0) dp[i][j]=dp[i-1][j]+10;
                    else dp[i][j]=min(dp[i-1][j]+10,dp[i][j]);
                }
                if(j<ma-3&&dp[i-1][j+3]!=0) dp[i][j]=min(dp[i][j],dp[i-1][j+3]);
            }
        }
        if(i==3)
        {
            if(dp[i][1]==0) dp[i][1]=25;
            else dp[i][1]=min(25,dp[i][1]);
        }
        if(i-3>0)
        {
            for(int j=1; j<ma; j++)
            {
                if(dp[i-3][j-1]!=0)
                {
                    if(dp[i][j]==0) dp[i][j]=dp[i-3][j-1]+25;
                    else dp[i][j]=min(dp[i-3][j-1]+25,dp[i][j]);
                }
            }
        }
        if(i==5)
        {
            if(dp[i][2]==0) dp[i][2]=37;
            else dp[i][2]=min(37,dp[i][2]);
        }
        if(i-5>0)
        {
            for(int j=2; j<ma; j++)
            {
                if(dp[i-5][j-2]!=0)
                {
                    if(dp[i][j]==0) dp[i][j]=dp[i-5][j-2]+37;
                    else dp[i][j]=min(dp[i-5][j-2]+37,dp[i][j]);
                }
            }
        }
    }
    long long Min=(long long)dp[n][0];
    for(int i=1; i<ma; i++)
    {
        if(dp[n][i]!=0&&Min>dp[n][i]) Min=(long long)dp[n][i];
    }
    cout << Min*1000;
}