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

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

 

문제 설명

 

 

본 문제는 백준의 2293번 문제 동전 1입니다.

 

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

 

조합을 의식하며 주어진 동전으로부터 어느 값을 구할 수 있는 모든 경우의 수를 구하란 문제입니다.

사용 동전의 개수는 무한하며 조합을 의식하여야하기에

 

4란 값을 구하기 위한 1, 2, 1 와 1, 1, 2는 같은 경우로 취급하여야합니다.

 

 

 

 

 

 

해결 과정

 

 

최적해를 구하는 문제이기에 다이나믹 프로그래밍으로 풀 수 있을 것이라 생각이 들었습니다.

처음에는 익숙한 방식인 Top down 방식의 재귀를 통해 DP를 구성하려하였는데

이 방식은 조합을 의식하지 않아 다른 방법을 찾았습니다.

각 동전들은 K라는 임의의 값을 만들기 위해 K - 동전의 경우의 수를 경우의 수로 가지게 됩니다.

 

모든 동전의 종류 (1, 2, 3)

선택한 동전 = 3, K= 5

5 - 3 = 2, 2의 경우의 수는 (1, 1), (2)로 2

3이라는 동전을 사용하고 5란 값을 만들 수 있는 경우의 수는 2입니다.

 

이 개념을 확장해 각 동전마다 그 동전에서부터 원하는 값 K 까지 그 동전을 사용하였을 때의 경우의 수를 더해줍니다.

 

모든 동전에서 이 과정을 끝내면 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];

    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = coins[i]; j <= k; ++j) {
            dp[j] += dp[j - coins[i]];
        }
    }

    cout << dp[k];
}

 

 

 

 

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

 

다이나믹 프로그래밍 문제는 어려운 것 같습니다!!

 

 

 

 

 

 

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

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