백준(BOJ) 다이나믹 프로그래밍 - 동전 1 (2293) - Gold5

문제

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

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

입력

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

출력

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

문제 해결

해당 문제는 알고리즘 수업을 들었을 때 다이나믹 프로그래밍에 가장 기본적인 형태라고 배웠던 기억이 났다. 문제를 보자마자 DP로 접근해야하 한다는 생각은 했지만 접근방법이 익숙하지 않아 상당히 어려웠다... 일단 문제에서 K원의 거스름돈을 갯수의 제한이 없는 N개의 동전(동전의 금액은 다름)을 이용하여 경우의 수를 계산하는 문제로 DP테이블을 갱신하면서 문제를 해결해야 한다. 또 하나 주의해야하는 점은 골드 문제 답게 메모리 계산도 신경써야 한다는 점이다. 

int : 4 바이트
long long : 8 바이트
vector<ll> dp(K+1, 0);: long long 변수 K+1개 사용 (8 bytes * (K+1))
vector<ll> changes(N, 0);: long long 변수 N개 사용 (8 bytes * N)

16 bytes (N, K) + 8 * (K+1) bytes (dp 배열) 
	+8 * N bytes (changes 배열) + 16 bytes (i, j) = 40 + 8K + 8N bytes
MB로 변환시 위 계산 값 / (1024^2)를 해주면 된다.

제일 처음 2차원 배열로 dp 테이블을 갱신했을 때는 메모리 초과를 피할 수 없었다. 위 식처럼 메모리 계산을 했을 경우 2차원 dp테이블을 사용하는 경우 아래와 같은 계산식에 의해  N = 100, K = 10000인 경우 메모리 사용량은 약 8MB가 된다.

vector<vector<ll> >dp(N+1, vector<ll>(K+1, 0));: 2차원 vector 배열 (8 bytes * (N+1) * (K+1))

메모리 사용량 = 16 + 8 * (100+1) * (10000+1) + 8 * 100 + 24 bytes
             = 16 + 8080808 + 800 + 24 bytes
             = 8081636 bytes

메모리 사용량 = 8081636 / (1024^2) MB
             ≈ 7.71 MB

제한 조건인 4MB를 한참 초과하게 된다. 따라서 1차원 배열로 해결해야 한다.

 

일단 2차원 배열이든 1차원 배열이든 문제 해결 방식은 다음과 같다.

 

1. dp 테이블은 만들고 거스름돈이 0원인 경우 아무런 동전도 사용하지 않는 방법 1개가 존재

-> 거스름돈이 0원이라 아무런 동전을 사용하지 않는 경우를 위해서 1추가

 

2.N개의 동전을 전체 보면서 테이블을 갱신

- 현재 가장 작은 가치의 동전부터 테이블 갱신 

-> 만약 거스름돈이 2원인데 현재 가지고 있는 동전의 최소 가치가 3원이라면 굳이 반복문을 돌지 않아도 되므로 최소동전의 가치부터 시작

for(ll i = 1; i <= N; i++){
	for(ll j = changes[i-1]; j <= K; j++){
    // dp[j]에 dp[j - changes[i-1]]을 더함으로써, 현재 동전의 가치를 이용하여 합이 j가 되는 경우의 수를 갱신.
		dp[j] += dp[j - changes[i-1]];
	}
}

- 현재 j번째 테이블의 값 = 현재 j번째 테이블 값 + 현재 j번째 테이블의 값 - 현재 동전의 가치

ex) 문제와 같이 거스름돈은 10원이였다고 가정하고 현재 가지고 있는 동전은 1원,2원,5원 이라고 가정해보자

 

i -> 1, j->1(현재 가장 작은 가치의 동전부터 시작)

 

dp[1]에는 처음 0이 저장되어 있음 

- dp[1] = 0 + dp[1 - 1] => 거스름돈이 0원일 때 이미 경우의 수를 1개 추가했으므로 거스름돈이 1원이면 아무런 동전을 사용하지 못하는 경우가 아닌 1원을 사용한 경우로 바뀌지만 똑같이 값은 1이다.

 

dp[2]에는 처음 0이 저장되어 있음

- dp[2] = 0 + dp[2-1] ==  dp[2] = 0 + dp[1]

거스름돈이 1원의 경우의 수를 넘겨 받는다 -> 어차피 같은 1원 동전을 사용하므로

 

dp[3]에는 처음 0이 저장되어 있음

- dp[3] = 0 + d[3-1] == dp[2] = 0 + dp[2]

거스름돈이 1원의 경우의 수를 넘겨 받는다 -> 어차피 같은 1원 동전을 사용하므로

...

dp[10]에는 처음 0이 저장되어 있음

- dp[10] = 0 + dp[10-1] == dp[10] = 0 + dp[9]

거스름돈이 9원의 경우의 수를 넘겨 받는다 -> 어차피 같은 1원짜리 동전 사용

i ->2 j->2 (2원 동전 테이블 갱신)

#-- dp[1]은 2원으로 거슬러 주지 못하므로 pass 

 

dp[2]에는 이전 1원의 경우의 수 "1"이 저장되어 있음 

- dp[2] = 1 + dp[2-2] == dp[2] = 1 + dp[0]

 => 1원을 사용하여 2원을 거슬러줄 수 있는 경우 + 1, 2원을 이용하여 2원을 거슬러줄 수 있는 경우 

 

dp[3]에는 이전 1원의 경우의 수 "1"이 저장되어 있음 

- dp[3] = 1 + dp[3-2] == dp[3] = 1 + dp[1]

1원을 사용하여 3원을 거슬러줄 수 있는 경우 + 1, 2원을 이용하여 3원을 거슬러줄 수 있는 경우 

 

dp[6]에는 이전 1원의 경우의 수 "1"이 저장되어 있음 

- dp[6] = 1 + dp[6-2] == dp[6] = 1 + dp[4]

1원을 사용하여  8원을 거슬러줄 수 있는 경우 + 1, 2원을 이용하여 4원을 거슬러줄 수 있는 경우 

 

dp[8]에는 이전 1원의 경우의 수 "1"이 저장되어 있음 

- dp[8] = 1 + dp[8-2] == dp[8] = 1 + dp[6]

1원을 사용하여  8원을 거슬러줄 수 있는 경우 + 1, 2원을 이용하여 6원을 거슬러줄 수 있는 경우 

...

 

dp[10]에는 이전 1원의 경우의 수 "1"이 저장되어 있음 

- dp[10] = 1 + dp[10-2] == dp[10] = 1 + dp[8]

1원을 사용하여  9원을 거슬러줄 수 있는 경우 + 1, 2원을 이용하여 거슬러줄 수 있는 경우 

 

i ->2 j->5 (5원 동전 테이블 갱신)

 

dp[10]에는 이전 2원의 경우의 수 "6"이 저장되어 있음 

- dp[10] = 6 + dp[10-5] == dp[10] = 6 + dp[5]

1,2원을 사용하여  10원을 거슬러줄 수 있는 경우 + 1,2,5원을 이용하여 5원을 거슬러줄 수 있는 경우 

 

위처럼 동전이 증가함에 따라 이전에 계산했던 동전들의 경우의 수 + 현재 자신을 포함해서 거슬러 줄 수 있는 경우의 수를 계산하여 DP테이블을 갱신하는 방식으로 해결해야 한다.

 

전체코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt" , "r" ,stdin);

    ll N, K;
    cin >> N >> K;

    // dp 배열 초기화. dp[i]는 합이 i가 되는 경우의 수를 나타냄.
    vector<ll> dp(K+1, 0);
    dp[0] = 1; // 합이 0이 되는 경우는 아무 동전도 사용하지 않는 경우 1가지 방법이 존재.

    // 동전의 가치를 입력받아 정렬한 후 사용.
    vector<ll> changes(N, 0);
    for(ll i = 0; i < N; i++)
        cin >> changes[i];
    sort(changes.begin(), changes.end());
    
    // 각 동전의 가치를 사용하여 가능한 경우의 수를 누적하여 계산.
    for(ll i = 1; i <= N; i++){
        for(ll j = changes[i-1]; j <= K; j++){
            // dp[j]에 dp[j - changes[i-1]]을 더함으로써, 현재 동전의 가치를 이용하여 합이 j가 되는 경우의 수를 갱신.
            dp[j] += dp[j - changes[i-1]];
        }    
    }

    // 합이 K가 되는 경우의 수 출력
    cout << dp[K] << "\n";
    return 0;
}

2차원 배열로 인한 메모리 초과 ㅠㅠ