ShaShaKa Dev Note

동전 1

16 August 2019

문제 : https://www.acmicpc.net/problem/2293

이번은 더 이상 사용되지 않는 값을 버림으로써 공간 복잡도를 향상시키는 문제를 풀어보도록 하겠습니다.

#include<stdio.h>

static int* arr;
static int* dp;

int main(void) {

	int N, TOTAL;

	scanf("%d %d", &N, &TOTAL);

	dp = new int[TOTAL + 1];

	arr = new int[N];

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &arr[i]);
	}

	dp[0] = 1;

	for (int i = 0; i < N; i++)
	{
		for (int k = 0; k <= TOTAL; k++)
		{
			if (k - arr[i] >= 0)
			{
				dp[k] += dp[k - arr[i]];
			}
		}
	}

	printf("%d", dp[TOTAL]);

	return 0;
}

여러 동전의 합으로 만들 수 있는 값의 경우의 수를 구하는 문제입니다.
1,2의 동전으로 3을 만든다고 하면 아래와 같이 풀이할 수 있습니다.
f(1,3) = 동전 1로 3을 만들 수 있는 경우의 수
f(2,3) = 동전 1,2로 3을 만들 수 있는 경우의 수
f(2,3) = f(1,3) + f(2,1) = f(1,3) + f(1,1)

만약 1,2의 동전으로 6을 만든다고 하면 아래와 같이 나타낼 수 있습니다.
f(2,6) = f(1,6) + f(2,4) = 2를 쓰지 않고 만드는 경우의 수 + 2를 하나 쓰고 나머지값인 4를 1,2를 모두 써서 만들 수 있는 경우의 수
f(2,4) = f(1,4) + f(2,2) 이므로 이미 f(2,4)에는 f(2,2)가 포함되어 있으므로 f(2,6)을 구할 때는 포함시키지 않습니다.
위와 같이 구현하여 마지막 dp 값을 return해주도록 합니다.