[백준] 2293번 - 동전 1 / C++

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

 

코드

#include <iostream>

using namespace std;

int N;
int K;
int coin[101];
long long money[100001];

void init()
{
	int i, j; 

	money[0] = 1;
	for (i = 0; i < N; i++)
	{
		for (j = coin[i]; j <= K; j++)
		{
			money[j] += money[j - coin[i]];
		}
	}
}

int main()
{
	int i;

	cin >> N >> K;
	for (i = 0; i < N; i++)
	{
		cin >> coin[i];
	}
	init();
	cout << money[K] << endl;
	return 0;
}

 

프로그래머스의 거스름돈과 같은 문제이다.

[프로그래머스] 거스름돈 / C++

 

링크

2293번: 동전 1

inbdni/Baekjoon