백준 달나라 토끼를 위한 구매대금 지불 도우미 17212번

문제

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

해결방법

이것은 유명한 동전문제

풀이 -> dp[i] 현재 합이 i인 동전일때 최대 or 최소 사용한 동전의 갯수

• a + b + c | conin[j] => 이들의 합이 j일 경우 a + b + c는 == i - coin[j]랑 동일하다

• 어떤 coin의 종류를 선택하냐(1, 2, 5, 7)에 따라서 앞에 dp[i-coin[j]]의 값이 달라진다. 그래서 모든 경우를 해보면된다.

• 점화식은 dp[i] = min(dp[i], dp[i - coin[j]) + 1;

• 시간복잡도는 o(n)

정답소스

#include <bits/stdc++.h>

using namespace std;

int coin[5] = { 0, 1, 2, 5, 7 };
int n;
int dp[100001];
//dp[i] = min(dp[i], dp[i-coin[j]] + 1);

void init() {
    for (int i = 0; i <= n; i++) {
        dp[i] = 200000;
    }
    dp[0] = 0;
}
int main() {

    cin >> n;

    init();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 4; j++) {

            if (i >= coin[j]) {
                dp[i] = min(dp[i], dp[i - coin[j]] + 1);
            }
        }
    }

    cout << dp[n];
    return 0;
}