2293. 동전 1 (Python)

2293번: 동전 1

 

풀이

 1차원 dp를 사용하여 문제를 해결할 수 있다. dp[value]는 value를 만들 수 있는 동전 조합의 수를 의미한다. dp 배열의 모든 값을 0으로 초기화하여 만든 후 dp[0]은 1로 설정한다. 이는 가치 0을 만들 수 있는 조합은 아무 동전도 사용하지 않는 하나의 경우의 수가 있기 때문이다. 문제의 점화식은 다음과 같다. value는 현재 살펴볼 가치의 합을 의미하고 coin은 현재 사용할 동전의 가치를 의미한다.

 

dp[value + coin] += dp[value]

 

 문제의 예제를 생각해보자.

  동전을 사용하여 가치의 합 2를 만들 수 있는 경우는 (1원 2개), (2원 1개) 이렇게 2가지 경우가 있다. 그렇기 때문에 dp[2]에는 2가 저장되어 있다. 이제 동전 5를 사용하는 경우를 보자. value 2에 동전 5를 사용하면 가치가 7이 된다. value 7을 만들 수 있는 경우의 수에 (1원 2개, 5원 1개), (2원 1개 5원 1개)에 대한 경우의 수를 추가할 수 있다. 이와 같이 dp[value + coin]에 dp[value]에 저장되어 있는 수를 더해주면 dp[value + coin]을 만들 수 있는 총 경우의 수를 구할 수 있다.

 

코드

if __name__ == '__main__':
    N, K = map(int, input().split())
    dp = [0 for _ in range(K+1)] # dp[n]: n의 가치를 만들 수 있는 동전 조합 경우의 수
    dp[0] = 1 # 0원을 만들 수 있는 경우의 수는 하나(아무 동전도 사용하지 않는다)

    for _ in range(N):
        coin = int(input())

        for value in range(K+1):
            # 현재 value에 현재 coin을 사용했을 때 K를 초과하면 탐색할 필요 없음
            if value + coin > K: 
                break
                    
            dp[value + coin] += dp[value]

    print(dp[K])