[BOJ] 13302번: 리조트

13302번: 리조트

풀이

dp[i][j] = j개의 쿠폰을 가지고 i일까지 있는데 드는 최소 비용.

 

처음에 쿠폰이 거슬렸는데 dp 배열을 2차원으로 두고 하니깐 한결 쉬워졌다. 재귀로 짰는데 for문으로도 짜보고 싶지만 잘 모르겠다.

코드

처음으로 3항 연산자의 감사함과 왜 있어야 하는가에 대해 진심으로 깨닫게 되었다...

#include <cstdio>
#include <algorithm>
using namespace std;

const int MN = 100 + 1;
int N, M, dp[MN][MN / 2]; // dp[i][j]는 i일까지 j개 쿠폰 가지고 있는 최소 가격 수.
bool chk[MN];             // 쉬는 날인지 확인

int f(int day, int coupon)
{
    if (day > N)
        return 0;
    if (dp[day][coupon] == -1)
        dp[day][coupon] = chk[day] ? f(day + 1, coupon) : min({coupon >= 3 ? f(day + 1, coupon - 3) : f(day + 1, coupon) + 10000, f(day + 3, coupon + 1) + 25000, f(day + 5, coupon + 2) + 37000});
    return dp[day][coupon];
}

int main()
{
    scanf("%d %d", &N, &M);
    for (int i = 0, get; i < M; ++i)
    {
        scanf("%d", &get);
        chk[get] = true;
    }
    fill(dp[0], dp[101], -1);
    printf("%d\n", f(1, 0));
    return 0;
}