[BOJ] 2293 - 동전 1

[BOJ] 2293 - 동전 1

문제

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

예제 입력

3 10
1
2
5

예제 출력

10

문제 해결

이 문제를 풀기위해서 어떤 값을 dp 배열로 잡을까 생각하다가 해당 금액을 만드는 경우의 수를 남는 방법을 이용해서 풀었다.

1. 우선 동전 개수만큼 순회를 하면서 입력을 받는다.
2. k원의 값까지 i를 순회하면서 i의 값이 입력받은 가치의 동전보다 작다면 dp[i - (입력받은 동전의 가치)] 의 값과 현재 dp[i] 값을 더해 dp[i] 에 대입한다.

예를 들어 동전의 가치가 5이고 원하는 돈의 합이 10이라고 하면 5의 이상 인 값인 5와 10까지는 0+5, 1+5, 2+5, 3+5, 4+5, 5+5 로 만들 수 있기 때문에 dp[i] = dp[i-(입력 받은 가치)] + dp[i] 을 한 것이다.

위 과정을 반복하면 dp[k]에 k의 최대 가지수가 담기게 된다.

python 코드

n, k = map(int, input().split())
dp = [0] * 10001
dp[0] = 1
for _ in range(0, n):
    su = int(input())
    for i in range(0, k+1) :
        if su <= i :
            dp[i] = dp[i] + dp[i - su]

print(dp[k])

Test Case

32 9336
2055
7284
3713
3810
6052
4874
996
1129
6352
6295
200
1848
4337
6826
4543
1737
3341
9030
3354
2426
4643
5136
6988
6787
213
5126
5156
3597
3792
354
6626
1713
current value :  440
----------------------
62 7899
1018
3757
1651
2816
236
6141
5543
6891
219
6671
7563
3622
2004
7505
2753
4734
1410
2045
1899
3162
6119
3720
7893
4744
5196
207
6017
6791
7264
5097
2227
524
2602
4619
1356
3826
6830
639
7728
2832
7473
772
878
1918
7825
2449
2315
2941
5850
211
1109
6436
878
803
7320
1620
6241
6222
7369
4232
1201
1388
current value :  159217
----------------------
11 5439
4401
3746
2047
5133
3977
3451
4184
366
4659
1815
1528
current value :  0
----------------------
72 1227
346
637
432
556
855
262
978
934
818
94
1206
642
680
748
697
877
968
705
1078
654
34
67
422
649
670
281
980
581
172
313
918
35
1181
414
432
1184
917
300
1045
463
968
817
197
349
298
1144
831
941
374
1006
343
1012
421
1037
817
383
350
1142
268
69
879
706
777
39
719
374
541
724
71
55
57
547
current value :  988989
----------------------
23 4048
3110
1532
2000
1360
619
330
3998
1778
3299
2515
425
786
3520
839
1886
2445
1112
1105
227
1901
118
3756
2075
current value :  78
----------------------

느낀점

해결하는데 조금 시간이 걸렸던 문제였다. 천천히 동전을 넣을수 있는 경우를 생각하니 풀렸다.