[백준_2293] 동전 1

 

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

2293번: 동전 1

 

문제 요약 : 동전 조합으로 중복 없는 경우의 수를 만들어라

---

[예제 분석]

다이나믹 프로그래밍으로 풀 것이고, 결과적으로 "count[i] += count[i - coin];" 이라는 로직이 나왔는데, 이 로직을 설명하는 글을 작성해 보려고 한다.

 

예제로 주어진 것은 동전 1, 2, 5 로 10을 만드는 경우의 수 이다.

 

1.

일단 count[0] , 0 을 만드는 경우의 수는 아무것도 선택하지 않는 경우의 수라 1 값을 저장해둔다.

 

2.

1원 동전만 사용해 1~10을 만드는 경우의 수는 각각 1가지라, count[1] ~ count[10]까지 1을 저장해둔다, 아래 사진 참고

 - 이 말도 이해가 안된다면 ?

1원 동전만 사용해 1원 만들기 : 1원동전 1개 사용 → count[1] = 1

1원 동전만 사용해 2원 만들기 : 1원동전 2개 사용 → count[1] = 1

.... 이런 식으로 1원 동전만 사용해 10원 만들기 : 1원 동전 10개 사용 → count[10] = 1 까지 저장해준다.

 

그렇다면 표는 다음과 같다

3. 2원 동전과 1원 동전을 사용했을 때 경우의 수를 구해보자. 다음 사진의 표와 같다

그래서 합계에는 1번 동전만 만드는 경우의 수와 합쳐준다.

 

4. 다음은 5번 동전도 사용하는 경우의 수를 구해보자

 

5. 그러면 도식화를 해야 하는데, 각 동전을 하나씩 순서대로 고려하면서, 해당 동전을 사용하여 각 금액을 만들 수 있는 방법을 만들어야 한다. count 배열은 각 금액을 만드는 방법의 수를 저장하는 역할이다.

 

이를 통해 count[5] 가 계산되는 과정을 👀 관찰해보자

---

<예시>

- 1원 동전을 사용하는 경우

1원부터 시작해 각 금액을 만드는데 1원만 사용하는 경우를 찾는다. 

 

- 2원 동전을 사용하는 경우

이제 2원을 사용할 수 있어 2원을 사용하여 만들 수 있는 경우의 수를 만든다

2원 동전을 한 번 사용해서 3원을 만드는 경우(count[3]에서 이미 계산된 값)에 2원 동전을 추가한다.

2원 동전을 두 번 사용하면 4원(count[2])에 2원을 추가해 6원까지 계산할 수 있으므로, 5원을 만드는 데는 count[3]에서 계산된 값에 2원 동전을 하나 더 추가하는 경우를 포함한다.

count[5]에는 이제 1원 동전 5개, 2원 2개와 1원 1개의 조합이 포함되어있다... count[5] + count[4] (1 + 1) 따라서 count[5]는 2가 저장되게 된다

 

- 5원 동전을 사용하는 경우

이제 5원도 사용할 수 있다, 5원 한개로 5원 만들기

이제 count[5]에는 1) 1원 동전 5개, 2) 2원 2개와 1원 1개, 5원 동전 한개 사용 : 3가지 방법을 포함한다

 

그래서 맨 처음 for문을 다음과 같이 작성했다 : 1, 2, 5를 선택했을때! 

for (int coin : coins) {}

 

 

⭐️⭐️⭐️ 이 안쪽에 들어가야 할 for문이며 가장 핵심이 되는 로직이다. 위에 서술했지만 하나하나 보겠다

for (int i = coin; i <= K; i++) {
        count[i] += count[i - coin]; // 현재 금액을 만드는 방법의 수에 동전을 추가하여 만들 수 있는 방법의 수를 누적
}

 

coin : 1원 선택할 경우의 수, 1부터 10까지 반복

1원으로 1원 만드는 경우는 동전 1개 선택하는 경우

count[i] += count[i - coin] 이 되는 이유를 본격적으로 설명하겠다.

1. 1원으로 1원 만들기

• 동전 1개를 선택하여 1원을 만들기 : 한가지 경우의 수 밖에 없음, 따라서 count[1]은 1

2. 1원으로 2원 만들기

• 동전 1개를 선택하여 2원 만드려면 이전에 1원을 만드는 경우의 수를 활용해야 한다.
• 1원으로 1원을 만드는 경우의 수는 1개이므로, 1원을 이미 만드는 방법이 1가지 있다. 이를 이용하여 1원을 더 선택하면 2원이 되고,  count[2]는 1원을 선택하는 경우의 수(1)와 이전에 저장된 count[1]의 값(1)을 더한 2가 된다.

3. 1원으로 3 만들기

• 이전에 1원을 선택하여 1원을 만드는 경우의 수는 1개
• 이 경우를 이용하여 1원을 더 선택하면 2원. 그리고 이를 다시 이용하여 1원을 더 선택하면 3원이 된다
• 따라서 count[3]은 1원을 선택하는 경우의 수(1)와 이전에 저장된 count[2]의 값(2)를 더한 3이 된다

coin : 2원 선택할 경우의 수 2 ~ 10까지 반복

2원을 만드는 경우의 수는 1원 2개, 2원 1개로 2가지이다. 

 

1. 2원으로 2원을 만드는 경우 : 

• 동전 1개를 선택하여 2원을 만들기, 이 경우는 방법이 하나라 count[2] 는 1이 된다

2. 2원으로 3원 만드는 경우 : 

• 2원 하나, 1원 하나 선택하는 경우 : 1원으로 1원을 만드는 경우의 수는 count[1]에 이미 저장되어있다. 이제 2원을 선택하는 경우의 수(1)와 이전에 저장된 count[1]의 값을 더해 줘 count[1]은 2가 됩니다.
• 따라서 count[3]은 2원을 선택하는 경우의 수 (1개) 와 이전에 저장된count[1]의 값을 더한 2가 된다

coin : 5원 선택할 경우의 수 5 ~ 10까지 반복

1. 5원으로 5원을 만드는 경우:

• 동전 1개를 선택하여 5원을 만든다. 이 경우는 하나의 방법이 있습니다. 따라서 count[5]는 1이 된다.

2. 5원으로 6원을 만드는 경우 : 

• 1원으로 1원을 만드는 경우의 수는 1개이며, 이 경우를 이용하여 1원을 더 선택하면 2원이 된다.
• 2원으로 2원을 만드는 경우의 수는 1개이며, 이를 이용하여 2원을 더 선택하면 4원이 된다.
• 따라서 count[6]은 5원을 선택하는 경우의 수(1)와 이전에 저장된 count[1]의 값(1)을 더한 2와 이전에 저장된 count[2]의 값(1)을 더한 3을 합친 3이 된다.

3. 5원으로 7원을 만드는 경우 : 

• 1원으로 2원을 만드는 경우의 수는 2개, 이 경우를 이용하여 1원을 더 선택하면 3원.
• 2원으로 3원을 만드는 경우의 수는 2개, 이 경우를 이용하여 2원을 더 선택하면 5원.
• 따라서 count[7]은 5원을 선택하는 경우의 수(3)와 이전에 저장된 count[2]의 값(1)을 더한 4와 이전에 저장된 count[3]의 값(2)을 더한 5를 합친 9가 된다.

count[i]는 현재 금액을 만들기 위해 coin을 선택하는 경우의 수를 누적해 간다. 이전에 coin을 선택하여 만든 금액의 경우의 수를 활용하여 현재 금액을 만드는 방법의 수를 계산한다.

---

위의 접근 방식을 통해 count[i]를 바꿀 때 마다, count[i - coin]의 값이 이미 coin을 사용하여 i - coin을 만드는 데 필요한 모든 경우의 수를 계산한 상태로 저장되어 있기 때문에, 해당 값에 coin을 추가하여  i원을 만드는 새로운 방법을 계산할 수 있다.

 

전체 코드는 다음과 같다

package src.com.company.week3.day4;

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

public class BJ_2293_동전 {
    /**
     * 메모리 : 14596KB, 시간 : 140ms
     * */
    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[] coins = new int[N];
        int[] count = new int[K + 1]; // 동전 만드는 방법의 수 : 0원 ~ 10원 만들어야 하니까 공간 11개(즉 K+1개 필요함)

        // 값 넣기
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            coins[i] = Integer.parseInt(st.nextToken());
        }
        // 0원을 만드는 방법은 아무것도 사용 안함..(한가지라 1도 설정)
        count[0] = 1;
        
       for (int coin : coins) {
            for (int i = coin; i <= K; i++) {
                count[i] += count[i - coin]; // 현재 금액을 만드는 방법의 수에 동전을 추가하여 만들 수 있는 방법의 수를 누적
            }
        }

        //System.out.println("count 배열 : " + Arrays.toString(count));
        // 출력 : count 배열 : [1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10]
        System.out.println(count[K]);
    }
}