[프로그래머스] 거스름돈

링크

https://programmers.co.kr/learn/courses/30/lessons/12907#

프로그래머스

풀이

 

Finn이 n 원을 거슬러 줄 방법의 수를 구하는 문제이다.

 

모든 동전으로 0원을 만들 수 있는 방법은 동전을 하나도 사용하지 않았을 때 이므로 1가지이다.

 

1원으로 n원까지 만들 수 있는 경우의 수는 모두 1가지이다. n원을 1원으로 만들기 위해서는 1원 * n개를 사용해야 되기 때문.

 

2원으로 2원을 만들기 위해서는 1원 *2와 2원 *1 방법이 있다.  2가지

           5원을 만들기 위해서는 1원 * 5 , 1*3와 2원 *1 , 1원 *1와 2원* 2 방법이 있다.  3가지.

 

5원도 위의 방식대로 경우의 수를 구할 수 있다

 

 

 

 

 

 

위의 표를 토대로 dp 식을 세울 수 있게 된다.

 

dp [거스름돈 금액] = dp[거스름돈 금액] + dp[거스름돈 금액 - 사용할 동전의 금액]

위의 dp 식을 이용하면 결과를 구할 수 있다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 101000
const int INF = 2000000000;
const int MOD = 1000000007;
using namespace std;

typedef long long int ll;

int dp[SIZE];
int solution(int n, vector<int> money) {
	dp[0] = 1;

	sort(money.begin(), money.end());
	for (auto m : money) {
		for (int i = 1; i <= n; i++) {
			if (i - m < 0) continue;
			dp[i] = (dp[i] + dp[i - m])%MOD;
		}
	}

	return dp[n]%MOD;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n = 5;
	vector<int> money = { 1,2,5 };

	cout << solution(n, money);

}