백준 2293 동전1

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

2293번: 동전 1

<문제>

 

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

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

 

<입력>

 

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

 

<출력>

 

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

 

<제한조건>

0.5초, 4MB

 

<풀이>

이렇게 제한조건이 빡빡하게 달려있는 문제가 제일 난이도가 높은거 같다..

제한조건이 0.5초, 4MB로 Brute Force로는 해결이 힘들거라고 판단했고,

그에 따라 DP를 먼저 생각하게 되었다.

 

DP의 경우의 수를 2개로 나눠 생각했는데

1. DP[i][j] 는 i번째 동전까지 자유롭게 사용해, 사용한 동전들의 합이 j개 되도록 하는 경우의 수

2. i번째 동전을 (0 ~ i-1) 번째 동전들의 합으로 표현 가능한 경우의 수.

 

여기서 1번이 더 직관적이고 점화식을 생성하기 편해 보여서 1번으로 접근했다.

DP[i][j] = DP[i-1][j] + DP[i][j - C[i]] (C[i]는 i번째 동전의 가치)

 

초기조건은 어떤 동전을 가지고 있든, k가 0인 경우, 동전을 내지 않는다  라는 1가지 경우의 수만 존재한다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;


int main(void) {

	int n, k, i, j;
	int arr[100], DP[100][10001] = { 0, };

	scanf("%d %d", &n, &k);
	for (i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	sort(arr, arr + n);
	// 동전의 가치는 100,000 보다 작거나 같은 자연수
	// 구하는 최대 가치는 10,000

	// DP[i][k]는 i번째 동전까지 사용해 합이 k가 되는 경우의 수

	 
	for (i = 0; i < n; i++) {
		DP[i][0] = 1; // 0원인 경우, 아무 동전도 내지 않는 경우의 수가 항상 존재
	}

	for (i = 0; i < n; i++) {
		for (j = 1; j <= k; j++) {
			if (j >= arr[i]) {
				DP[i][j] = DP[i][j - arr[i]] + DP[i - 1][j];
				// 1. i번째 동전까지 활용한 더 작은 수
				// 2. i-1번째 동전까지만 쓴 경우
			}
			else {
				DP[i][j] = DP[i - 1][j];
			}
		}
	}

	printf("%d\n", DP[n - 1][k]);

	return 0;
}

 

그런데 위의 코드로 제출하게 되면 DP가 4MB를 넘어가기 때문에 백준의 테스트를 통과하지 못한다.

그래서 고민을 해본 결과, DP를 계산하는 과정에서 DP[i], DP[i-1]까지만 필요하기 때문에 

i를 구하는 과정에서 i-1번째 열을 덮어쓰면 된다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;


int main(void) {

	int n, k, i, j;
	int arr[100], DP[10001] = { 0, };

	scanf("%d %d", &n, &k);
	for (i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	sort(arr, arr + n);
	// 동전의 가치는 100,000 보다 작거나 같은 자연수
	// 구하는 최대 가치는 10,000

	// 1. 치환?
	// 2, DP 적용?
	// 2.1 DP[i][k]는 i번째 동전까지 사용해 합이 k가 되는 경우의 수

	DP[0] = 1; // 0원인 경우, 아무 동전도 내지 않는 경우의 수가 항상 존재
	
	for (i = 0; i < n; i++) {
		for (j = 1; j <= k; j++) {
			if (j >= arr[i]) {
				DP[j] += DP[j - arr[i]];
				// 1. i번째 동전까지 활용한 더 작은 수
				// 2. i-1번째 동전까지만 쓴 경우
			}
			// 아닌 경우에는 따로 업데이트할 필요 없음
		}
	}

	printf("%d\n", DP[k]);

	return 0;
}