[백준 자바 2293] 동전 1 (골드 5)

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

2293번: 동전 1

 

 

동적 계획법, 그중에 상향식(Tabulation)으로 풀었다. 

 

처음에는 백트래킹으로 풀어봤는데 시간초과가 났다. 메모리가 4MB 밖에 안 되어서 dp는 아니겠다 싶었는데 dp로 푸는 거였다. 

 

---

 

 

풀이에 사용하는 변수들과 입력이다. 

N, K는 각각 동전 개수와 만들어야 하는 금액이며, 동전을 받기 위해 리스트를 만들어 입력해주었고, 

동적 계획법으로 푸므로 dp를 0부터 K를 범위로 하는 정수 배열로 선언해주었고, 초기값을 초기화해두었다. 

 

dp[만들어야 하는 금액] = 금액을 만드는 경우의 수

dp는 위와 같다. 즉, K = 만들어야하는 금액이 1원이라면, 1원 동전만 쓰이므로 경우의 수는 1이다. dp[1] = 1. 

여기서 한 가지 짚고 가야할 점은 0원을 만들려면 아무 동전을 사용하지 않는 경우가 있으니, 어느 동전이든 dp[0] = 1 이다. 

 

그러면 1원인 동전을 가지고 K가 10일 때를 구해보면,

만들어야하는 금액	0원	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
1원 동전의 경우의 수	1	1	1	1	1	1	1	1	1	1	1

1원인 동전들로 1원을 만들든 10원을 만들든 경우의 수는 1개이다. 

 

 

 

그러면 1원과 2원 동전들로 만드는 경우의 수는?

만들어야하는 금액	0원	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
1원 동전	1	1	1	1	1	1	1	1	1	1	1
1원 + 2원 동전	1	1	2	2	3	3	4	4	5	5	6

먼저 2원 동전을 이용하려면 만들어야 하는 금액이 2원 이상이어야 하므로 1원은 변함이 없다. 

2원인 경우의 수는 1+1, 2 로 2가지다. 

3원인 경우의 수는 1+1+1, 1+2 로 2가지다.

4원인 경우의 수는 1+1+1+1, 1+1+2, 2+2 로 3가지다. 

 

 

 

그러면 1,2,5원 동전들로 만드는 경우의 수는, 

만들어야하는 금액	0원	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
1원 동전	1	1	1	1	1	1	1	1	1	1	1
1원 + 2원 동전	1	1	2	2	3	3	4	4	5	5	6
1원+2원+5원 동전	1	1	2	2	3	4	5	6	7	8	10

5원 동전을 이용하려면 만들어야 하는 금액이 5원 이상이어야 하므로 1,2,3,4원은 변함이 없다. 

5원이 되는 경우의 수는 기존의 1,2원 동전으로 만드는 경우의 수에 5원의 경우의 수를 더하면 된다. 

 

즉, 

새로 동전이 추가된 경우의 수 = 기존 동전들로 만든 경우의 수 + 현재 동전이 하나 추가되면서 생기는 경우의 수

이거를 다시 정리하면

dp[현재 동전][만들어야 하는 금액] = dp[기존 동전][만들어야 하는 금액] + dp[현재 동전][만들어야 하는 금액 - 현재 동전]
dp[i][k] = dp[i-1][k] + dp[i][k-coins[i]] 

이 된다. 

dp[현재 동전][만들어야 하는 금액 - 현재 동전] 인 이유는, 예를 들어 dp[1원+2원 동전][5원] 이라고 하면, 기존 dp[1원][5원] 에다가, 2원 동전으로 5원을 만들려면 기존에 이미 3원의 경우의 수가 있어야 하기 때문이다. 

만들어야하는 금액	0원	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
1원+2원	1	1	2	2	3	3	4	4	5	6	6

만들어야하는 금액	0원	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
1원+2원+3원	1	1	2	2	3	4	5	6	7	8	10

 

하지만 위 표에서 계산하는 방식을 적용해보면 1행의 1열에서 시작하여 오른쪽 끝으로 계산을 진행하고, 다음 2행에서는 1행의 값에다가 현재 행의 과거 열의 값을 더해서 계산한다. 이를 식으로 다시 나타내면,

dp[i][k] = dp[i-1][k] + dp[i][k-coins[i]] 은,
dp[i] = dp[i] + dp[k-coins[i]] 로 2차원 배열 -> 1차원 배열로 만들 수 있고, 이를 더 줄이면
dp[i] += dp[k-coins[i]] (k >= coins[i]) 가 된다. 

여기서 k가 동전의 값보다 커야 그 동전을 사용할 수 있으므로 (k >= coins[i]) 조건 역시 들어가게 된다. 

 

이를 이용하여 식을 세워보면 

i는 동전을 가져올 때 사용하고

j는 위의 (k>=coins[i]) 조건을 만족시키기 위해서

아예 그 동전값부터 시작하도록 했다. 

 

 

 

 

 

마지막으로 dp[K]를 출력해주면 답이 나오게 된다. 

 

---

 

전체 코드

 

import java.io.*;
import java.util.*;

public class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static int N;
    static int K;
    static List<Integer> coins;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = stoi(st.nextToken());
        K = stoi(st.nextToken());
        coins = new ArrayList<>(N);
        dp = new int[K + 1];
        dp[0] = 1;

        for (int i = 0; i < N; i++) coins.add(stoi(br.readLine()));

        for (int i = 0; i < N; i++) {
            for (int j = coins.get(i); j <= K; j++) {
                dp[j] += dp[j - coins.get(i)];
            }
        }

        System.out.println(dp[K]);
    }
}

 

참고자료

• https://lotuslee.tistory.com/113
• https://dragon-h.tistory.com/10