[BOJ] 백준 2294 동전 2 (문제 설명, 코드, C++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 백준의  2294번 동전 2 문제입니다.

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

 

n 가지의 동전이 있고 각 동전들을 사용해 k란 값을 만들기 위한 경우 중

동전의 수가 가장 적은 경우의 동전수를 찾아란 문제입니다.

 

조합을 염두에 두고 해결해야합니다.

 

 

해결 과정

 

 

조합을 염두에 두기에 가치가 젤 적은 동전부터 그 동전을 사용하여 만들 수 있는

K까지의 모든 값들의 경우의 수는 다음과 같이 구할 수 있습니다.

 

k = 5, 동전의 가치 3, 동전을 사용해 만들 수 있는 값 j (3 ~ k)

dp[i] k 가 i일 때 최소 동전수

 

dp[j] = dp[j - 3]  + 1(동전 3의 개수)

 

이 과정을 모든 동전에게 다 시행하며 기존의 동전의 개수가 더 적을 수 있습니다. 그래서 

dp[j] = min(dp[j], dp[j - 3] + 1) 다음과 같이 dp 배열을 채워나갈 수 있습니다.

 

조합을 염두에 두기에 작은 동전부터 자신의 가치부터해서 k까지의 값에 자신을 사용한다 염두에 두고

진행하면 조합을 고려한 채 풀어나갈 수 있습니다.

 

 

 

 

 

코드 전문

 

 

#include <iostream>
#include <algorithm>

using namespace std;

int n, k;
int coins[102];
int dp[10002];

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) 
        cin >> coins[i];

    for (int i = 0 ; i < 10002; ++i) dp[i] = 999999;
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = coins[i]; j <= k; ++j) {
            dp[j] = min(dp[j], dp[j - coins[i]] + 1);
        }
    }
    if (dp[k] == 999999) cout << -1;
    else cout << dp[k];
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

 

동전 1 문제에서 조금 변형한 문제네요!

 

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.