백준 2293 동전 1 (파이썬)

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

 

정답 코드

import sys
def solve():
    for coin in arr:
        for j in range(coin, K+1):
            dp[j] += dp[j-coin]

    print(dp[K])
    return

if __name__=="__main__":
    input = sys.stdin.readline
    N, K = map(int, input().split())
    arr = [int(input()) for i in range(N)]
    # dp[1]는 1개만 골랐을 때 경우의 수
    # dp[0]은 하나의 동전만으로 k원 만드는 경우의 수를 의미 = 1
    dp = [1] + [0]*K

    solve()

결과 및 정리

전형적인 DP 문제

메모리가 4MB라 1차원 배열까지만 DP를 선언해서 해결해야합니다.

 

dp[i]는 dp[i] + dp[i - coin] 으로 점화식을 나타낼 수 있는데

예를 들어 dp[2] = dp[2] + dp[0] 로 나타낼 수 있습니다.

이는 dp[2] = 1원으로 만든 2원을 의미하며 dp[0] = 2원 1개로 만든 경우의 수로 이는 1+1, 2의 경우를 나타냅니다