백준 2293 동전 1 (Python)

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

2293번: 동전 1

별로 어렵다고 생각하지 않았지만, 풀다보니 굉장히 어려운 문제였다.

단순하게 배열로 쭉 만들어서 더하며 나가면 된다고 생각했는 데, 구성이 같은 것들을 제외하느라 시간을 오래쓰게 되었다.

 

이해가 잘 될 수 있도록 보기를 통해 분석해보도록 하자.

보기는 1, 2, 5이 3가지 동전으로 10을 채우는 경우를 구하는 것이다.

 

경우의 수를 모두 구해보자.

5	5
5	2	2	1
5	2	1	1	1
5	1	1	1	1	1
2	2	2	2	2
2	2	2	2	1	1
2	2	2	1	1	1	1
2	2	1	1	1	1	1	1
2	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1	1

 

이렇게 10가지의 경우가 나오게된다.

이렇게보면 나누기로도 구할 수 있을 거 같은데, 일단 당연히 DP로 풀어야 하기에 생각해보지 않았다.

 

경우의 수가 중복이 되면 안되기 때문에 각 코인은 한 번씩 코인의 개수만큼 반복해야 한다.

일단 코인을 입력받으면, 해당 코인의 가치만큼의 경우의 수가 +1 되는 것이다.

 

그리고 1부터 목표가치만큼 진행하며, 만약 m의 가치의 경우의 수가 3이라면 m+(코인의 가치)의 가치에 해당하는 경우의 수도 3 늘어나게 되는 것이다.

 

이렇게 반복문을 진행해가면 된다.

 

import sys

n, k = map(int, sys.stdin.readline().split())

value = [0 for i in range(k+1)]

for i in range(n):
    coin = int(sys.stdin.readline().strip())
    if coin <= k:
        value[coin] += 1
    for t in range(1, (k+1) - coin):
        value[t+coin] += value[t]

print(value[-1])