백준 알고리즘 2293번: 동전1

문제 정보

---

 

2293번: 동전 1

 

 

핵심

---

이전 글과 동일한 Dynamic Programming을 활용하여 풀이하는 문제이다

기존 문제 대비 점화식 세우는것이 개인적으로 조금 어렵다고 느꼈기 때문에 최대한 처음 문제를 접하는 입장에서 문제를 풀이해보도록 하겠다

 

문제 유형 잡기

일단 해당 문제는 서두에 설명했듯 DP 알고리즘을 사용하는 문제이다

이를 생각하게 된 몇가지 근거는, 먼저 일반적으로 많이 풀어봤을 법한 잔돈 문제 등은 Greedy 알고리즘이지만 이는 최적의 해를 구해나가는 방식으로 풀이되는 문제이기 때문에 위 문제와는 맞지 않다

또한 모든 경우의 수를 계산하기에는 동전의 개수가 너무 많으므로 DFS와 같은 모든 경우의 수를 계산하는 알고리즘을 사용하기에도 옳지 않다

우리가 구해야 하는 K원이 되는 경우의 수에서 각각의 경우의 수를 구할 때에는 이전 값들(K-1원, K-2원 ...)의 경우의 수와 큰 연관이 되므로(만약 1원, 2원짜리 동전을 가지고 있다면, K-2원을 만들 수 있는 경우의 수에 2원을 만들 수 있는 경우의 수인 2를 더해주면 답이 될 것임)

이처럼 큰 문제인 K원에 집중하지 않고 작은 문제들(K-N원)으로 나누어 풀이하는 방법을 선택할 수 있게 된다

 

점화식 세우기

3 10
1
2
5

위 예시에서 우리는 총 3가지의 동전을 가지고 있다

1

2

5

위 3가지 동전을 사용해서 10원이 되도록 하는 경우의 수를 구하면 된다

 

자, 처음 우리가 해야할 일은 DP 배열의 값이 나타내는 값을 정하는 일이고 DP[i]는 i원을 만들기 위해 가능한 경우의 수의 합을 의미한다고 설정하였다

 

1원만 사용하여 1-10원까지 만들 수 있는 경우의 수를 먼저 생각해보자 (DP)

1

1

1

1

1

1

1

1

1

1

모든 경우를 1원만을 가지고 만들 수 있고, 각각의 경우의 수는 1개이다

 

여기서 2원을 함께 사용하여 만들 수 있는 경우의 수를 생각해 보면 어떨까?

일단, 만드는 가치의 합이 2원보다 작은 경우에는 2원과 함께 만들 수 없으므로(1원은 만들 수 없음), 기존 값을 그대로 가져온다

1

2

2원의 경우에는(DP[2]) 1원을 통해 만들수 있는 경우의 수 1개와, 2원 1개를 통해 만들 수 있는 경우의 수 1개를 더한 값인 2가 된다

 

1

2

2

3원의 경우에는(DP[3]) 1원을 통해 만들 수 있는 경우의 수 1개와, 1원과 2원을 하나씩 사용하여 만들 수 있는 경우의 수 1개를 더한 값인 2가 된다

 

1

2

2

3

4원의 경우에는(DP[4]) 1원을 통해 만들 수 있는 경우의 수 1개, 그리고 이외 2가지 경우(1+1+2, 2+2) 총 3가지 경우가 존재한다

 

자, 여기서 보면 비슷한 점들이 눈에 띄는데 위 예시로 알아보면

-> 4원의 경우에는(DP[4]) 1원을 통해 만들 수 있는 경우의 수 1개, 그리고 이외 2가지 경우(1+1+2, 2+2) 총 3가지 경우가 존재한다

1원을 통해 만들 수 있는 경우의 수 -> 기존 DP[4]

이외 2가지의 경우 -> 1+1 +2, 2 +2 -> 2원을 만들 수 있는 경우의 수

(new) DP[4] = (prev) DP[4] + (new) DP[2]

 

위와 같은 식으로 결론지을 수 있을 것이다

 

정리

위 예시를 이어서 6원을 만드는 경우의 수를(1원과 2원을 사용하여) 구하면

6원을 만드는 경우의 수는 결국, 기존 1원만을 사용하여 만들 수 있는 6원의 경우의 수 1개 +

1원과 2원을 사용하여 4원을 만들 수 있는 경우의 수가 되는 것이다

 

1원만을 사용한 DP[] (1 to 10)

1

1

1

1

1

1

1

1

1

1

 

1원, 2원을 사용한 DP[]

1

2

2

3

3

4

4

5

5

6

 

1, 2, 5원을 사용한 DP[]

1

2

2

3

4

5

6

7

8

10

 

3가지 동전으로 10원을 만들기 위해서 총 10가지 경우(DP[10]) 가 존재한다는 것

 

다만, 여기서 설명하지 않았던 부분은 DP[0]에 관한 부분이다

dp[i] = dp[i] + dp[i - num];

점화식을 다음과 같이 작성하려면, 가장 첫번째 경우인 i=num인 경우에서

num원을 만들기 위한 num원이 가지는 경우의 수는 1개라는 전제 조건이 있어야 한다

 

1원과 2원짜리 동전으로 2원을 만들기 위한 계산 과정은

- 1원만 사용하여 2원을 만드는 기존 경우의 수 1개 ( 1 + 1 )

- 2원만을 사용하여 2원을 만드는 새로운 경우의 수 1개 ( 2 )

 

총 2가지가 되어야 하기 때문이다

따라서, 모든 새로운 동전에서도 DP[0]의 값은 1이어야 새로운 동전만을 사용한 경우의 수를 올바르게 더해주어

계산 결과를 보장할 수 있기 때문에 아래와 같이

dp[0] = 1;

0번째 dp 배열의 값은 1로 설정해 주어야 하며 이 값은 변경되지 않아야 한다.

 

 

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] input = br.readLine().split(" ");
    int N = Integer.parseInt(input[0]);
    int K = Integer.parseInt(input[1]);

    int[] numbers = new int[N];
    for (int i = 0; i < N; i++) {
      numbers[i] = Integer.parseInt(br.readLine());
    }

    int[] dp = new int[K + 1];
    dp[0] = 1;

    for (int num : numbers) {
      for (int i = num; i <= K; i++) {
        dp[i] = dp[i] + dp[i - num];
      }

      for (int n : dp) {
        System.out.print(n + " ");
      }
      System.out.println();
    }
    System.out.println(dp[K]);
  }
}

 

Source Code on GitHub

---