[C++] 백준 1106 - 호텔

https://www.acmicpc.net/problem/1106

풀이

dp 문제이다.

dp에 많이 약해서 dp 연습을 이제 좀 시작하려고 한다.

얼마나 약하냐면, 골드 4인데도 dp 식이 아직 잘 안떠오른다.

 

dp리스트는 1차원으로, dp[i] = (정확히 i명 모으는데 드는 최소 비용)이다.

초기에 i = 0을 제외하고는 전부 무한대로 초기화한다.

한 번에 최대 100명까지 들어올 수 있으므로 dp의 길이는 C+100정도면 충분할 것이다.

각 도시별로 다음을 반복하면 된다.

j가 0부터 C+100-gain 인 동안,

dp[j+gain] = min(dp[j+gain], dp[j] + cost)

 

이게 되는 이유는, j가 0부터 점점 커지므로, 중복이 자연스럽게 카운팅된다. (직접 그려보면 안다.)

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int C; cin >> C;
    int N; cin >> N;
    int dp[C+100] = {};
    for (int i = 1; i < C+100; i++) dp[i] = 999999;
    for (int i = 0; i < N; i++) {
        int cost, gain; cin >> cost >> gain;
        for (int k = 0; k < C+100 - gain; k++) {
            dp[k+gain] = min(dp[k+gain], dp[k] + cost);
        }
    }
    int ans = 999999;
    for (int i = C; i < C+100; i++) {
        ans = min(ans, dp[i]);
    }
    cout << ans;
}