[BOJ] 1106_호텔

호텔

문제 링크: https://www.acmicpc.net/problem/1106

1106번: 호텔

 

i를 i개의 손님 유치 수라 하자.
dp[i]는 손님 유치를 하는데 드는 최소비용이라고 정의할 수 있다.

 

 

현재 상태의 손님 유치의 수를 c라 하면, 다음의 단계에서 들었던 비용과 현재의 비용의 합이 c를 유치하는데 드는 비용이 된다.
그 중 가장 최소인 값이 dp[i]의 값이 될 것이다.

 

Dynamic Programming의 방법 중 Top-Down 방식을 채택하여 다음과 같이 코드를 구성했다.

 

• 정답코드

    #include<iostream>
    using namespace std;
  
    #define min(a, b) (a<b ? a : b)
    #define maxInt 10000000
  
    int dp[2000] = { 0, };
    int info[21][2];
  
    int DP(int c, int n) {
        if (c < 0)
            return 0;
        else if (c == 0)
            return cost;
        else if (dp[c] > 0) 
            return dp[c];
        else{
            int m = maxInt;
            for (int i = 0; i < n; i++)
                m = min(m, DP((c - info[i][1]), n) + info[i][0]);
            dp[c] = m;
            return dp[c];
        }
  
    }
  
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
  
        int c = 0, n = 0;
        scanf_s("%d%d", &c, &n);
        memset(dp, -1, sizeof(dp));
  
        for (int i = 0; i < n; i++)
            scanf_s("%d%d", &info[i][0], &info[i][1]);
  
        printf("%d", DP(c, n));
        return 0;
    }

---