[프로그래머스] Level 3 : 거스름돈

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

프로그래머스

 

DP를 통해 풀었다.

 

1. 문제의 거슬러 줘야 하는 최대 금액만큼 배열을 선언하고, 모두 0으로 초기화한다.
이 배열은 각각의 금액마다 거슬러 줄 방법의 수를 저장한다. (캐시)
다만, 0일 경우에는 무조건 나누어 떨어진다는 의미로 1로 초기화한다.

2. 총 화폐를 순회하고, 화폐마다 최대 금액으로 순회한다.

3. 현재 화폐가 현재 금액보다 큰 경우는 넘어간다.

4. DP의 점화식은 캐시[현재 금액] += 캐시[현재 금액 - 현재 화폐] 이다.

 

 

알고리즘을 예제의 최대 금액 5, 화폐 1, 2, 5로 설명한다.

 

먼저, 최대 금액만큼 배열을 선언하는 이유이다.

이는 DP의 캐시를 사용하기 위함인데, n원에 해당되는 값을 얻기 위해서는 그 아래의 가격이 만들어질 수 있는 경우의 수를 알아야 이를 통해 계산 없이 바로 값을 얻을 수 있다.

 

예를 들어, 1원과 2원을 가지고 4원을 만들어 보자.

1원으로 1~4원을 만들 수 있는 방법은 각각 1개씩이다.

그럼 각 캐시 배열에 1씩 추가한다. 그 의미는 해당 화폐로는 해당 금액을 만들 수 있는 방법이 1개라는 의미이다.

 

2원으로는 1원을 만들 수 없으니 넘어가고, 2~4원을 만들어 보자.

2원을 보면, 화폐 2원으로 만들 수 있다. 즉, 캐시 2원에 경우의 수가 1개 더 추가되어 총 2개가 된다.

이때 사용하는 점화식이 바로, 캐시[현재 금액] += 캐시[현재 금액 - 현재 화폐]이다.

 

이렇게 쭉 따라가서, 각각 화폐 1, 2, 5원이 금액 1~5원을 만들 수 있는 방법을 모두 찾아놓으면 금액 5원을 만들 수 있는 방법은 1, 2, 5원의 경우의 수를 모두 더한 값으로 저장이 된다.

#include <string>
#include <vector>
#include <cstring>
using namespace std;

int Cost[100000];

int solution(int n, vector<int> money) {
	memset(Cost, 0, sizeof(Cost));
	Cost[0] = 1;

	for (int i = 0; i < money.size(); ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (money[i] > j) continue;
			Cost[j] += Cost[j - money[i]];
		}
	}
	return Cost[n];
}