[백준 2293번] 동전1 (C++) (시행착오부터 DP를 떠올리기까지의 아주 자세한 사고과정 기록)

1. 문제

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

2293번: 동전 1

이미지 예시

중복을 허락하여 해당 동전을 만들 수 있는 경우이므로 자연수 분할, 즉 중복 조합문제이다.

2. 풀이

아이디어(시행착오)

동전 n개로 k원을 만들 수 있는경우의 수를 구하는 문제이다. 언뜻 보기엔 일반적인 DFS로 재귀를 이용한 top - down방식으로 풀 생각이 들 수 있다.

 

예들 들어 1, 2원짜리 동전을 가지고 4원을 만드는 경우  3원(4 - 1원)에 1원을 더한 것과 2원(4 - 2원)에 2원을 더한 것으로 나타낼 수 있다.

따라서 4원을 만드는 경우의 수 =  3원을 만드는 경우의 수 + 2원을 만드는 경우의 수이다.

이런식으로 확장하면,

3원을 만드는 경우의 수 = 2원을 만드는 경우의 수 + 1원을 만드는경우의 수,

2원을 만드는 경우의 수 = 1원을 만드는 경우의 수 + 0원을 만드는 경우의 수로 확장할 수 있다.

 

점화식은 다음과 같다.

D(k) = ΣD(k - C(i)) (i = 1, 2, 3, ..., n)

 

이를 구현한 코드는 다음과 같다.(궁금하면 클릭!)

DFS로 모두 탐색한 코드

#include<iostream>

using namespace std;

int n, k;
int D[10000];
int coin[100];
int money(int N) {
	if (N == 0) {
		D[0] = 1;
		return D[N];
	}
	else if (N < 0) return 0;

	if (!D[N]) for (int i = 0; i < n; i++) D[N] += money(N - coin[i]);
	return D[N];
}

int main(void) {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> coin[i];
	}

	cout << money(k) << "\n";
	for (int i = 0; i <= k; i++) cout << D[i] << " ";
	return 0;
}

 

 

하지만 이  풀이에는 문제가 있다. 문제의 조건을 살펴보면 "사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다"라는 조건이 있다. 

 

예를 들어서 1, 2, 5원으로 4원을 만들 때 1을 두번, 2를 한번 쓰는 경우만 해도 다음과 같이 세 가지 중복이 생긴다.

 

• 3원에 1을 더한 경우(즉, 3원을 만드는 경우의 수)

1 + (1 + 1 + 1)
1 + (1 + 2)
1 + (2 + 1)

 

• 2원에 2를 더한 경우(즉, 2원을 만드는 경우의 수)

2 + (1 + 1)
2 + (2)

 

재귀함수를 이용한 top - down방식은 탐색 과정에서 중복에 상관없이 모든 경우를 고려하기 때문에 순열의 형식을 가지기 때문이다.

재귀 함수를 이용한 top - down 방식으로 탐색한 경우(빨간색 선이 중복 탐색한 경우이다.)

 

따라서 일반적인 DFS를 이용한 top - down 방식을 이용하면 중복이 생긴다.(필자도 이거때문에 엄청 고민했다!) 그러므로 문제에서 의도한대로 조합의 방법으로 개수를 세야 한다.

---

조합을 적용한 풀이

조합을 이용하여 점화식을 세워야 DP를 이용하여 효율적으로 개수를 셀 수 있다. 아까의 과정에서처럼 1과 2가 순서가 다를 때에 중복카운팅되는 것을 막으려면 동전이 겹치지 않도록 경우를 나누어서 따로 세어야 한다. 다음과 같이 말이다.

1. 1원만 사용하는 경우
2. 2원만 사용하는 경우
3. 5원만 사용하는 경우
4. 1원과 2원만 사용하는 경우
5. 1원과 5원만 사용하는 경우
6. 2원과 5원만 사용하는 경우
7. 1원, 2원, 5원 모두 사용하는 경우

 

하지만 이렇게 나누면 시간복잡도가 너무 커지므로 더 적절한 방법을 찾아야 한다.

 

처음부터 4원을 만드는 과정을 하나하나 나열하여 규칙을 발견해보자.

 

1. 1원을 만드는 경우

(0원) + 1원

 

→ 그냥 1원 하나만으로 만들 수 있다.

따라서 1가지이다.

 

2. 2원을 만드는 경우

(1원)  + 1원
(0원)  + 2원

 

→ (이미 만들어진 1원)에 1원을 추가하는경우와 (이미 만들어진 0원)에 2원을 추가하는 경우의 합이다.

따라서 2가지이다.

 

3. 3원을 만드는 경우

(2원) + 1원 
(1원)  + 2원

 

→ (이미 만들어진 2원)에 1원을 추가하는 경우와 (이미 만들어진 1원)에 2원을 추가하는 경우의 합으로 볼 수 있다.

여기서 중복이 생긴다!!!! 
(이미 만들어진 2원)에 1원을 추가하는 순간 (이미 만들어진 1원)에 2원을 추가하는 경우와 중복이 생긴다.
이 중복을 파악하고 제거하면서 점화식을 만드는 것이 이 문제의 핵심이다.

 

왜 중복이 생기는지 더 자세히 알아보기 위해 3원이 되는 모든 과정을 다 살펴보자.

 

(이미 만들어진 2원)은 다음과 같이 두 가지였다.

(1원)  + 1원
(0원)  + 2원

 

여기서 1원을 더하는 순간, (이미 만들어진 2원)에 1원을 추가하여  3원을 만드는 경우는 다음과 같이 두 가지로 구성된다.

(1원 + 1원) + 1원
(2원 + 0원) + 1원

 

그리고 이제 남은 (이미 만들어진 1원)에 2원을 추가하는 경우 다음의 한 가지가 더 추가된다.

(1원 + 0원) + 2원

 

바로 여기서 3원을 만드는 경우의 수에는 (1원 + 2)원과 (2원 + 1원)이라는 경우가 다르게 처리되어 두 번 계산되는 것이다.

여기서 중복된 경우는 앞으로 4원, 5원, 6원, ...을 셀 때 모두 누적되어 카운팅된다.

 

확신을 얻기 위해 4원을 만드는 경우를 한번 더 살펴보자.

 

4. 4원을 만드는 경우

(3원) + 1원
(2원) + 2원

 

→ (이미 만들어진 3원)에 1원을 추가하는 경우와 (이미 만들어진 2원)에 2원을 추가하는 경우의 합이다. 

여기서도 마찬가지로 4원은 3원의 경우에서 더블카운팅된 중복이 누적되어 추가로 (1원 + 2원 + 1원), (2원 + 1원 + 1원), (1원 + 1원 + 2원)이 누적된다.

 

이를 해결하기 위해 우리는 다음과 같은 해결책을 생각할 수 있다.

 

이를 해결하기 위해서는 매 경우마다 무조건 오름차순으로만 더해져야 한다.
즉, 다음 동전을 더할 때에 자신보다 큰 동전이 있으면 안된다.
다시말해서, 앞에 2가 더해진 경우 다음으로 넘어가는과정에서 1이 더해지면 안된다.

 

예를 들어 3을 만들 때에 (1 + 1 + 1)과 (1 + 2)만 세어주어야

뒤에서 4를 만들 때에 (1 + 1 + 1 + 1), (1  + 1 + 2), (2 + 2)만 셀 수 있다. 

 

따라서 3에서 4로 넘어갈 때에 오름차순으로 더해주기 위하여 크게 두 가지로 나눌수 있다.

(1원보다 큰 동전이 포함안된 3원) + 1원
(2원보다 큰 동전이 포함안된 2원) + 2원

 

마지막으로 모든 경우에 대해 성립하는지 확인하기 위해 5원짜리 동전이 추가된 경우도 한번 확인해보자.

 

5. 5원을 만드는 경우

1원, 2원, 5원으로 5원을 만드는 경우 현재 동전이 정해지는 경우는 크게 세 가지로 나눌 수 있다.

(1원보다 큰 동전이 포함안된 3원) + 1원
(2원보다 큰 동전이 포함안된 2원) + 2원
(5원보다 큰 동전이 포함안된 0원) + 5원

 

→ 5원은 (1 + 1 + 1+ 1 + 1), ( 1+ 1 + 1+ 2), (1 + 2 + 2), (0 + 5)원로 알맞게 나오는 것을 알 수 있다.

 

이를 일반화하면 다음과 같다.

 

앞에 2가 더해진 경우 다음으로넘어가는과정에서 1이 더해지면 안된다.

앞에 5가 더해진 경우 다음으로넘어가는과정에서 2 또는 1이 더해지면 안된다.

...

∴ 앞에 vi원의 동전이 더해진 경우 다음으로 넘어가는 과정에서 vi원 이상만 더해져야 조합의 경우로 계산할 수 있다.

 

∴ 따라서 i번째 동전을 C(i)라고 할 때, k원이 정해지는 경우는

 

 C(1)원으로만 이루어진 동전에 C(1)원을 추가하는 경우

    + C(1), C(2)원으로만 이루어진 동전에 C(2)를 추가하는 경우

             + C(1), C(2), C(3)원으로만 이루어진 동전에 C(3)를 추가하는 경우

    ...

                            + C(1), C(2), C(3), ..., C(n)원으로만 이루어진 동전에 C(n)를 추가하는 경우

의 합이다.

 

이때 새로운 동전이 추가될 때마다 앞의 누적된 값들이 중복계산된다. 예를 들어,

2원이 추가될 때 1원만 사용한 경우가 사용되고

5원이 추가될 때 1원만 사용하는 경우와 1, 2원을 동시에 사용한 경우가 다시 계산된다.

만약 여기에 7원이 추가된다면 1, 2, 5원을 동시에 사용한 경우가 다시 계산될 것이다.

바로 이 과정에서 새로운 C(i)원이 추가될 때 앞의 값들이 중복계산되므로 DP를 이용하여 memoizaion하고 다음 값을 구할 때에 기록한 값을 이용하는 것이다.

 

그러면 두 가지 방법으로 확장해가며 표를 table을 채울 수 있게 된다.

 

[memozation 방법]

1. C(i)원으로 조합을 만들 수 없는 경우에는 앞의 값을 그대로 가지고 온다.
2. C(i)원으로 조합을 만들 수 있는 경우에는 이 전의 값에 C(i)로 만드는 경우를 더한다.
3. 기저 사례를 설정하기 위해 0일 때에도 설정해준다.

 

이를 적용하여 8원을 만드는 경우를 표로 나타내어보면 다음과 같다.

k원      C(i)	0	1	2	3	4	5	6	7	8
0	1	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	3	3	4	4	5
5	1	1	2	2	3	4	5	6	7

 

예를 들어서 5원짜리로 동전을 만드는 경우를 살펴보면,

k = 4까지는 1, 2원으로 만들 수있는 경우 뿐이므로 1, 2원을 사용했을 때의 값을 그대로 갱신해주고 k = 5부터는 5원을 추가할 수 있으므로 새로 갱신해 주었다.

 

또한 C(i)가 1원일 때에 or 1원을 만드는 경우에 대해서도 일반성을 유지하기 위해

k = 0인 경우를 base로 두어 1로 초기화해두었으며

0원으로 k원을 만드는 경우도 따로 1가지로 설정해 두었다.

 

여기서 알 수 있듯이 점화식을 이용하여 DP를 풀 때에 초기값 설정이 매우 중요하다.

 

D(i, k)를 i번째 동전으로 k원을 만드는 경우의 수라고 할 때 이를 바탕으로 만든 점화식은 다음과 같다.

if ( c(i) < k ) → D( i, k ) = D( i-1, k ) 
if ( c(i) >= k ) → D( i, k ) = D( i-1, k ) + D(i, k - C(i))
(i = 1, 2, 3, ..., n)
단, C(0) = 0, C(i, 0) = 1

 

하지만 문제의 조건을 보면 동전의 개수가 최대 100이므로 배열의 최대 크기는 101 x 10001 =  약 10의 6승이다.

int는 4byte이므로 배열은 메모리에서 약 4 x 10의 6승 byte 이다. 이를 MB로 환산하면 약 4MB이므로 메모리 제한을 초과한다. 따라서 2차원 배열로 D[101][10001]을 그대로 사용하면 메모리 초과가 떠버린다.

 

 

어차피 전의 값은 다음 값을 갱신한 뒤에는 필요없으므로  메모리 절약을 위해 새로운 행을 사용하지 않고 다음 C(i)로 넘어갈 때 그 전의 배열을 덮어버리면 된다. 다음과 같이 말이다.

 

C(1) 실행 결과

k원      C(i)	0	1	2	3	4	5	6	7	8
1	1	1	1	1	1	1	1	1	1

 

C(2) 실행 결과

k원      C(i)	0	1	2	3	4	5	6	7	8
2	1	1	2	2	3	3	4	4	5

 

C(3) 실행 결과

k원      C(i)	0	1	2	3	4	5	6	7	8
0	1	1	2	2	3	4	5	6	7

 

이렇게 다음의 동전이 추가될 때마다 덮어버리면 1차원 배열로 충분히 만들 수 있다.

 

3. 구현

아까 언급한 점화식의 일반성을 위해서

D(0) = 1로 설정해 두었으며

배열의 index0을 추가로 사용하였으므로C배열의 최대 크기는 101칸, D배열의 최대 크기는 1001칸이다.

#include<iostream>

using namespace std;
int coin[101];
int D[10001];


int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> coin[i];

	D[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <=k; j++) {
			if(j>=coin[i]) D[j] += D[j - coin[i]];
		}
	}
	cout << D[k];

	return 0;
}

 

4. 느낀점

처음 문제를 접했을 때에는 정말 어려웠다. DP적사고를 기르기에는 좋은 문제라고 생각한다.

여기서 느낀 DP적 사고란 어떻게 기록해서중복을 제거할까?? 라는 생각을 하면서  중복되는 모든 경우를 따지고 이를 바탕을 점화식을 만드는 것이다.

여기에다 메모리 초과까지 생각하면서 점화식의 초항설정까지 생각해 주어야 하는 생각할 것이 많은 문제였다.