[BOJ] 2293 동전 1 - Java

1. 문제 링크

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

2293번: 동전 1

---

2. 문제 풀이

 DP 문제를 좀 많이 풀어보고 싶어서 얼마 전부터 풀기 시작했습니다. 하지만?? 피보나치를 벗어나는 점화식을 만들어내는 건 아직 힘들더라구요. 처음엔 DP 문제가 아닌 줄 알았지만 시간제한이 0.5초라 브루트포스..같은 건 안될 거 같습니다. 

유의!

 동전의 구성은 같지만 순서만 다른 경우가 생기는데 그동안 만들어낸 조합들을 어떻게 하나하나 체크를 다 하겠어요.. 그러니 이 문제는! DP가 맞다- 이 말입니다.
 경우의 수는 다행히 정수 범위를 넘어서지 않아서 long을 써야한다던가 그럴 필요는 없어요. 그래서, 점화식은 어떻게 구하느냐. 어차피 동전의 구성이 같다면 같은 경우의 수니까, 특정한 금액을 맞추기 위해서 조건에 맞는 경우의 수를 새로 구할 필요가 없습니다. 기존에 구해놓았던 경우의 수를 활용하면 됩니다. 그것이 DP니까.

DP니까 DP입니다.

 문제의 예제1로 주어졌던 조건들을 봅시다. 동전이 3개(1, 2, 5)이고, 10원을 만드는 경우의 수를 구해야 합니다. 먼저 아래에 있는 실제 코드의 결과 값을 활용해서 설명해 보겠습니다.

  

    
    
    
    
  
      1 2 3 4 5 6 7 8 9 10(원)
1원 : 1 1 1 1 1 1 1 1 1 1 
2원 : 1 2 2 3 3 4 4 5 5 6 
5원 : 1 2 2 3 4 5 6 7 8 10

 먼저 제일 먼저 들어온 1원으로 만들 수 있는 경우의 수는 각 단계별로 하나씩 만들 수 있습니다.

• 1원으로 1원을 만들 수 있는 경우의 수 : 1 (1)
• 1원으로 2원을 만들 수 있는 경우의 수 : 1 (1 + 1)
• 1원으로 3원을 만들 수 있는 경우의 수 : 1 (1 + 1 + 1)
• . . .
  
  

1원으로만 경우의 수를 구해보았는데 뭔가 느껴지지 않나요. 점화식의 냄새가..? 킁킁..

... 아직 느껴지지 않다면 다음 단계로 넘어가면서 이해를 해봅시다.

 아까 1원으로만 만들었던 경우의 수들을 바탕으로 2원을 추가해서 새로운 경우의 수를 만들 겁니다. 2원으로는 1원을 만들지 못하니, 2원부터 만들어 볼 것이구요. 일단, 2원은 2원 동전 하나로 만들 수 있으니, 기존 경우의 수에 1을 더해 줄 거예요. 자 그러면, 이제부터 시작입니다.

• 2원을 만들 수 있는 경우의 수 : 2 (1 + 1, 2)
• 3원을 만들 수 있는 경우의 수 : 2 (1 + 1 + 1, 1 + 2)
• 4원을 만들 수 있는 경우의 수 : 3 (1 + 1 + 1 + 1, 1 + 1 + 2, 2 + 2)
• . . .
  
  

 기존에 있던 경우의 수에서 2를 포함하는 경우의 수가 추가되었습니다. 새롭게 추가된 경우의 수를 자세히 살펴보니, 뭔가 규칙이 있는 거 같지 않나요? 2원을 만들 수 있는 경우의 수에 +2원이 추가된 상태로 4원이 만들어졌습니다. 대충 규칙을 찾은 거 같습니다. 뭔가 의심스럽다면 나머지 과정도 한번 직접 그려가며 따라가는 방법도 나쁘지 않다고 생각해요.

 새로운 경우의 수를 추가할 때, 현재 더해야 할 동전의 금액을 감산한 금액의 경우의 수를 더하는 규칙!

현재 동전이 들어있는 금액의 배열을 arr[]라 하고, 동전의 인덱스를 i라고 합시다. 그리고, dp[] 배열과 dp 배열의 인덱스를 j라고 합시다. 그렇다면, 점화식은 다음과 같습니다.

dp[j] = dp[j] + dp[j - arr[i]]
기존에 다른 동전들로 만들어졌던 경우의 수 + 새로운 동전을 추가하여 새롭게 만드는 경우의 수

 이해가 되시나요? 현재의 동전 하나로 만들 수 있는 수(1원으로 1원, 2원으로 2원 만들기)는 그냥 기존 배열의 값에 1을 더하면 되긴 합니다. 하지만 점화식대로 만들고 싶다? 그렇다면, 배열에서 사용하지 않는 공간(예로 들자면 0번째 인덱스)을 따로 만들어서 그 부분을 1로 설정하고, 점화식대로 코드를 작성하면 됩니다. 저는 전자의 방식으로 풀었습니다.

 

 참고로, 순서가 뒤집어져도 똑같은 경우의 수가 나오는지 한번 체크하는 것도 추천..!

잘 나오네유 ^=^

---

3. 소스 코드

  

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

public class BOJ2293 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken()), k = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(br.readLine());
        int[] dp = new int[k+1];
        for(int i = 0; i < n; i++){
            for(int j = 1; j <= k; j++){
                if(arr[i] == j)
                    dp[j]++;
                else if(arr[i] < j)
                    dp[j] += dp[j - arr[i]];
            }
        }
        System.out.println(dp[k]);
    }
}

3-1. 테스트 케이스

  

    
    
    
    
  
input :
1 1
1

answer :
1 

-----------
input :
1 1
2

answer :
0 

-----------
input :
3 10
5
2
1

answer :
10

-----------
input : 
100 10000
3
6
9
12
15
18
21
24
27
30
33
36
39
42
45
48
51
54
57
60
63
66
69
72
75
78
81
84
87
90
93
96
99
102
105
108
111
114
117
120
123
126
129
132
135
138
141
144
147
150
153
156
159
162
165
168
171
174
177
180
183
186
189
192
195
198
201
204
207
210
213
216
219
222
225
228
231
234
237
240
243
246
249
252
255
258
261
264
267
270
273
276
279
282
285
288
9640
9703
9856
9859

answer : 
2013845695

---

4. 한줄평

 DP는 여전히 어렵다.. 문제 이해하는데 40분이나 걸림.. 하지만 점화식을 만들기만 한다면 코드는 금방 작성함..