1. 문제 풀이
n 가지 종류의 동전으로 그 가치의 합이 k원이 될 수 있는 경우의 수를 구하는 문제이다. 각각의 동전은 몇개라도 사용할 수 있다.
(1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 으로 주어진다.
우선 해당 값을 만들 수 있는 경우의 수는 값의 배수 일때 1번.
순열으로 만들었을때 두가지 동전으로 만들 수 있는 경우의 수 = 이전 동전으로 만들 수 있는 경우의 수 + 현재 동전으로 만들 수 있는 경우의 수 가 되는것이다.
이것을 점화식으로 인덱스에 기록해가며 더해가면 해당 동전들로 가능한 경우의 수를 구할 수 있다.
처음 첫 인덱스에 값을 1로 설정하고 그 뒤를 0으로 초기화해 처음 coin의 값이 들어갈 때 1이 더해지도록 했다.
2. 코드
#include <iostream>
using namespace std;
int main(int argc, char const *argv[])
{
int n,k;
//동전 종류 수
cin >> n;
//가치
cin >> k;
int coin;
//가치크기 배열 1, 0 ... 초기화
int val[k + 1] = {1,};
for (int j = 0; j < n; j++)
{
cin >> coin;
//코인의 값을 받아 i에 설정, 코인의 값만큼 이전 인덱스 값을 더해가며 저장
for (int i = coin; i < k + 1; i++)
val[i] += val[i - coin];
}
cout << val[k] << endl;
return 0;
}
C++
복사
3. 채점 기록
메모리 : 2016KM / 0ms
