KOI 리조트 첨삭1

koi_resort_edit1.cpp

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int min( int a , int b)
{
	return a>b ? b : a;
}

int main()
{
    int n , m , day[101] , dp[101][201] = {} , ans = 2e9; // ans도 큰 수로 초기화
    scanf("%d %d", &n , &m );
    for( int i = 0 ; i < m ; i++ )
    {
    	int x;
    	scanf("%d", &x );
    	day[x] = 1;
    }

    for( int i = 0 ; i <= n ; i++ ) // 날짜는 n일까지, 따라서 i < n 대신 i <= n.
    	for( int j = 0 ; j <= 2*i ; j++ ) // i일까지 고려했을 때 가능한 쿠폰 수는 2*i개. 따라서 j <= 2*i.
    	{
    		dp[i][j] = 2e9;
    	}
    dp[0][0] = 0;

	for( int i = 0 ; i < n ; i++ )
		for( int j = 0 ; j <= 2 * i ; j++ ) // 위와 마찬가지 이유로 j <= 2*i.
		{
			if(day[i+1]==1) dp[i+1][j] = min( dp[i+1][j] , dp[i][j] ); // i+1일이 갈 수 없는 날일 때(day[i+1]==1) 이용권 구매 안함.
			else dp[i+1][j] = min( dp[i+1][j] , dp[i][j] + 10000 );
			for( int k = 1 ; k <= 3 ; k++ )
			{
				if( i+k > n ) break; // 날짜는 n일까지 존재
				dp[i+k][j+1] = min( dp[i+k][j+1] , dp[i][j] + 25000 );
			}
			for( int k = 1 ; k <= 5 ; k++ )
			{
				if( i+k > n ) break; // 날짜는 n일까지 존재
				dp[i+k][j+2] = min( dp[i+k][j+2] , dp[i][j] + 37000 );
			}
			if( j >= 3 ) dp[i+1][j-3] = min( dp[i+1][j-3] , dp[i][j] );
		}
	for( int i = 0 ; i <= 2*n ; i++ )
		ans = min(ans, dp[n][i]); // 마지막 날짜는 n일, 쿠폰 수는 0~2n. 따라서 dp[n][0..2n]의 최솟값을 ans에 갱신
	printf("%d", ans );
    return 0;
}