백준 2293번 동전 1

 

 

 

문제 보러가기 : https://www.acmicpc.net/problem/2293

 

 

2293번: 동전 1

 

 

이번 문제는 다이나믹 프로그래밍 문제였습니다.

 

 

 

《문제 풀이》

 

1. n가지 동전의 가치를 coinValue 배열로 입력받음

2. 가치의 합이 k원이 되는 경우의 수를 구하기 위한 dp 배열을 모두 0으로 초기화

3. dp[0]은 자신의 가치만으로 j원이 되는 경우의 수이므로 1로 세팅

4. 가치의 합이 j원이 되는 경우의 수와 자신의 가치를 뺀 가치의 경우의 수를 합함 ⭐️

5. n가지 동전의 가치의 합이 k원이 되는 경우의 수는 dp[k]

 

 

 

《C++ 코드》

 

#include <iostream>
#include <cstring>

using namespace std;

int n, k;
int coinValue[100], dp[10001];

// 가치의 합이 k원이 될 수 있는 경우의 수 구하기 
int countWayK() {
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i=0; i<n; i++) {
        for (int j=coinValue[i]; j<=k; j++) {
            dp[j] += dp[j - coinValue[i]]; // (현재의 가치 - 자신의 가치)가치를 만들 수 있는 경우의 수를 합해줌  
        }
    }
    return dp[k];
}

int main() {
    ios::sync_with_stdio(0);
	cin.tie(0);

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

    int result = countWayK();
    cout<<result;
    return 0;
}

 

 

개발 환경: Visual Studio Code

 

 

 

baekjoon - 정답 화면