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

2293번: 동전 1

문제

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

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

 

 

 

입력

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

 

 

 

출력

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

 

풀이과정

해당 문제는 "n개의 서로다른 동전이 주어질때 k라는 동전을 만들 수 있는 경우의 수는 몇가지인가?" 라는 문제였었다.

너무 못그렸다..

문제에 접근하는 과정이 생각보다 까다로웠던 거 같다.

정리를 해보자면 이 문제 역시 dp이다보니 이전의 값을 이용해서 현재의 값을 구하는 방식은 맞았었다.

동전의 종류 n을 각자 보는 방식으로 풀이가 이루어진다.

 

예시를 들어

2 10
1
2

형식으로 예시가 들어왔다고 가정을 해보고 1 ~ 6까지 구해보면

1 : 1 						: 1
2 : 1 1 | 2 					: 2
3 : 1 1 1 | 2 1 				: 2
4 : 1 1 1 1 | 2 1 1 | 2 2			: 3
5 : 1 1 1 1 1 | 2 1 1 1 | 2 2 1			: 3
6 : 1 1 1 1 1 1 | 2 1 1 1 1 | 2 2 1 1 | 2 2 2	: 4
.
.
.

형식으로 전개가 되는 방식이고, 위와 같은 모습에서 2의 배수마다 가짓수가 1씩 증가하는 모습을 확인할 수 있다.

위의 상황을 통해 현재사용하는 동전의 크기의 배수마다 값이 새롭게 갱신이 된다는 것을 확인할 수 있어서

2차원 배열 형식으로 점화식을 전개해보면

dp[y][x] = dp[y - 1][x] + dp[y][x - 현재 사용하는 동전의 크기] 라는 것을 볼 수 있고,

문제에서 요구하는 메모리의 크기가 4MB밖에 안되어서 1차원 배열 형식으로 줄여보자면
이전의 구한 [y - 1]의 값을 바탕으로 현재의 [y]값을 구상하는 방식이니

dp[n] = dp[n](이전의 구한 값) + dp[n - 현재 사용하는 동전의 크기] 형식으로 점화식을 세울 수 있다는 것을 확인 할 수 있었다.

code

#include <iostream>

int		coin[101];
int		dp[10001];

int main(void)
{
	int n, k, temp;

	std::cin >> n >> k;
	for (int i = 0; i < n; i++) {
		std::cin >> coin[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= k; j++) {
			temp = dp[j];
			if (coin[i] == j) dp[j]++;
			if (1 <= j - coin[i])
				dp[j] = temp + dp[j - coin[i]];
		}
	}
	std::cout << dp[k] << "\n";

	return (0);
}

 

후기

dp이긴하지만 이 문제는 평소에 풀던 dp와는 살짝 다르게 응용까지가 포함된 느낌이었다.

접근하기까지 많은 노력이 필요했던 문제같다.