백준 2293 자바 - 동전 1 (BOJ 2293 JAVA)

문제 : boj2293

 

 

1.

  우선 문제를 좀 더 간단히 변경해서 봐보자. 1,2,5의 가치를 가지는 동전이 있고, 그 가치의 합이 10이 되게 하려 한다. 그리고 문제와 다르게 동전의 구성이 같아도 순서가 다르면 다른 경우로 치고 생각해보자.

 

  그럼 1차원 배열을 활용한 dp로 아래와 같이 풀 수 있다. (냅색 문제처럼 풀면 된다.)

 

1.1 우선 초기값이다. dp[idx]는 1,2,5의 동전들을 가지고 idx의 가치를 가지는 경우의 수를 나타낸다. dp[0]은 실제론 불가하지만, 초기값으로 넣어준다. 그래야 동전 하나를 가지고 표현할 수 있는 경우에 대해서도 별도로 처리하지 않고 점화식 하나로 계산하기 편하다. (예를들어 2의 가치를 표현하려면 동전2짜리 하나만 쓸 수 있다. 식으로는 dp[2-2]이다. 따라서 dp[0]에 그냥 1을 넣어둔 것이다.)

 

1.2 이후 동전 1,2,5에 대해 각각 확인한다. idx 1부터 차례대로 10까지 dp[idx] = dp[idx-1] + dp[idx-2] + dp[idx-5] 의 점화식을 수행하면 된다. idx는 참고로 가치의 합이 10이 되게 하려 하므로 10까지만 있다. 결과는 다음과 같다.

 

1.3 말로설명하면 다음과 같다.

 

가치 1을 만들자!(idx 1) : 1짜리 동전 하나로 표현하는 한 가지 경우만 있다.

 

가치 2 : idx 1이 가치 1을 표현하는 경의의 수 이므로 거기에 동전 1을 더해주면 된다. 그리고 동전 2를 하나 써서도 표현할 수 있다.

 

가치 3 : 마찬가지로 가치 2의 가지수에 동전 1을 두면 되므로 일단 dp[2], 그리고 가치 1의 가지수에 동전2를 두면 되므로 dp[1]도 포함된다. 즉 dp[3-1] + dp[3-2] 이다.

 

...

 

가치 5 : 가치4에 동전1을 두는 경우 + 가치3에 동전2를 두는 경우 + 동전5를 하나만 두는 경우 = dp[5-1] + dp[5-2] + dp[5-5] 가 된다.

 

...

 

가치 10 : 마찬가지로 dp[10-1] + dp[10-2] + dp[10-5]로 처리하면 된다.

 

 

2.

  그런데 문제에서는 '사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.' 라고 조건을 뒀다. 그럼 '1'에서 어떻게 순서만 다른 것을 같은 경우로 칠 수 있을지 생각해봐야한다.

 

  만약 5를 표현하기 위해 1짜리 동전 3개와 2짜리 동전 1개를 썼다고 쳐보자. 이 때 모든 경우는

A. 1, 1, 1, 2

B. 1, 1, 2, 1

C. 1, 2, 1 ,1

D. 2, 1, 1, 1

의 4가지 경우가 있다.

 

  그리고 5를 표현하기 위해 1짜리 동전 1개와 2짜리 동전 2개를 쓴 경우는 다음과 같다.

A. 1, 2, 2

B. 2, 1, 2

C. 2, 2, 1

의 3가지 경우가 있다.

 

  그럼 단순히 생각해서 HashSet등을 활용해서 현재 나온 모든 순서쌍을 기억해서 처리할 수도 있겠다. 하지만 이 문제의 메모리 제한은 4MB 밖에 안되므로 불가하다.

 

  이걸 좀 더 간단하게 해결하는 방법은 위와 같이 여러가지가 경우가 있을 때, 저 중 하나의 순서쌍만 남기기 위한 규칙을 하나 정하면 된다. '직전에 사용한 동전보다 항상 더 가치가 같거나 큰 동전만을 사용한다.' 라는 규칙을 추가해보자. 그럼 5를 표현하기 위해 1짜리 동전 3개와 2짜리 동전 1개를 사용한 경우에 대해서는

A. 1, 1, 1, 2 -> 규칙에 맞는건 얘 뿐임

B. 1, 1, 2, 1

C. 1, 2, 1 ,1

D. 2, 1, 1, 1

 

그리고 5를 표현하기 위해 1짜리 동전 1개와 2짜리 동전 2개를 쓴 경우에도

A. 1, 2, 2 -> 규칙에 맞는건 얘 뿐임

B. 2, 1, 2

C. 2, 2, 1

 

  그럼 동일한 동전에 대해 순서만 다른 경우를 한가지로 제한할 수 있다! 하지만 생각은 나도 이걸 구현하긴 좀 어려운게 사실이다. 

 

 

3.

  '직전에 사용한 동전보다 항상 더 가치가 같거나 큰 동전만을 사용한다.'는 규칙을 구현해보자. 우선 이걸 위해 입력으로 주어진 동전의 가치를 오름차순으로 정렬해줘야 한다. 구현은 마찬가지로 dp로 할 수 있는데, 2차원 배열로 표현해야 한다.

 

arr[b]를 b번째로 작은 가치를 가지는 동전의 가치라 하자.

그리고 dp[b][a]를 'a가치를 표현하기위한 방법 중 arr[b]의 가치의 동전을 마지막에 사용한 경우의 수'라 하자. 참고로 arr[b][a]를 그냥 b의 가치의 동전을 마지막에 사용한 경우라 하지 않고 arr[b]의 가치라고 한 이유는, arr[b]는 최대 100개면 되지만 b는 최대 100,000이기 때문이다. 가치 a의 최대치는 10,000이므로 전자는 10000*100개짜리 배열로 표현가능하지만, 후자로 하려면 10000*100000개의 배열이 필요하다. 따라서 최대 100개짜리 배열인 arr을 추가해서 전자로 표현한 것이다.

 

 

3.1 그럼 예제 입력 1을 봐보자. 여기선 설명의 편의를 위해 배열에 arr[b]의 값 자체를 적어뒀다. dp[0][0]에 해당하는 열에는 '1.1'에서 했던것과 같이 편의를 위해 1을 기본값으로 넣어뒀다. 가치 1을 표현하기 위해 1의 가치를 가지는 동전을 썼다. 이 경우 위의 dp 정의에 따라 dp[0][1]만 1이 된다. 동전 1짜리를 마지막에 쓴 것이다.

 

3.2 이제 가치2를 표현하는 경우를 보자. 가치 2를 표현하기 위해 동전1을 사용하는 경우 dp[0][2-1]의 경우에서 동전1을 추가로 사용한다. 그리고 동전2를 사용하는 경우가 중요한데, dp[0][2-2]에서 자기보다 가치가 낮은 경우를 모두 더해줘야 한다. 이따 좀 더 살펴보다보면 이해할 수 있을 것이다. 그리고 동전5를 쓰는 경우는 dp[0][2-5]는 인덱스를 넘어가므로 당연히 패스한다.

 

3.3 가치3인 경우를 보자. 동전1을 추가해 가치3을 만들 수 있는 경우는, 동전1보다 가치가 작거나 같은걸 마지막에 사용한 가치 '3-1=2'인 경우에 동전1을 추가하는 것이다. 그리고 동전2를 추가해 만드는 경우는 동전2보다 가치가 작거나 같은걸 마지막에 사용한 가치 '3-2=1'인 경우에 동전 2를 추가하는 것이다.

 

3.4 가치5인 경우를 보자. 마찬가지고 동전1을 써서 가치5를 만드는 경우는 가치4에서 동전1 이하만 써서 만든 경우에 동전 1을 더한 경우이다. 순서대로 표현하자면 '1 1 1 1 1'을 쓴 경우이다. 동전2를 쓴 경우는 가치3에서 동전2 이하를 써서 만든 경우에 동전2를 더하는 경우로, '1 1 1 2'와 '1 2 2'의 두가지가 된다. 동전5를 쓴 경우도 이제 생겼다. 동전 5 하나만 쓴 경우이다.

 

3.5 가치7인 경우를 보자. 마찬가지로 동전1을 쓴 경우는 앞으로도 쭉 '1 1 1 1 ... 1'으로 한가지가 될 것이고, 동전2를 쓴 경우는 '1 1 1 1 1 2', '1 1 1 2 2', 1 2 2 2'의 3가지가 될 것이다. 동전5를 쓴 경우는 '1 1 5', '2 5'의 두가지가 된다. 정의한대로, 항상 이전보다 같거나 더 큰 동전만 사용한 경우를 세고 있다.

 

3.6 가치10인 경우를 보자. 마찬가지 방식으로 진행하면 된다. 최종적으로 idx 10 (열 10)에 있는 모든 값을 더한 1+5+4 = 10이 답이 된다.

 

이 방식으로 풀 경우 최대 O(K * N^2)으로 풀 수 있다. [가치 1~K까지 확인에 O(K) x 각 가치마다 모든 동전 확인 O(N) x 이전 가치에서 자기 이하의 모든 값 확인에 O(N)]

여기까지만 봐도 문제는 풀 수 있다.

 

점화식은 다음과 같다.

 

 

 

4.

  추가로 좀 더 줄여볼 수 있는데, 위의 점화식에서 시그마 부분을 빼버려서 O(KN)으로 계산 가능하다. '3'에서 봤던 배열을 각 열에대해 prefix sum 했다고 하고 다시 그려보자. 그럼 이전 가치에서 자기 이하의 모든 값 확인 대신에, 이전 가치에서 자신의 값 자체가 그 이전까지의 경우의수를 모두 포함하게 되므로 O(1)로 바로바로 구할 수 있다. 따라서 가장 우측 아래에 있는 값이 답이 된다.

  

이 경우 점화식은 다음과 같다.

 

이하 코드는 '4'의 방식으로 푼 코드이다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] coins = new int[n+1];
        for (int i = 1; i <= n; i++)
            coins[i] = Integer.parseInt(br.readLine());
        Arrays.sort(coins);

        int[][] dp = new int[n+1][k+1];
        for (int i = 1; i <= n; i++)
            dp[i][0] = 1;

        for (int value = 1; value <= k; value++) {
            for (int eachCoin = 1; eachCoin <= n; eachCoin++) {
                dp[eachCoin][value] = ( value-coins[eachCoin]<0 ? 0 : dp[eachCoin][value-coins[eachCoin]] ) + dp[eachCoin-1][value];
            }
        }
        System.out.println(dp[n][k]);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}