(백준 알고리즘 문제풀이) 2293번 동전 1

문제

문제 링크

 

문제 접근

• N가지 종류의 동전 -> 가치의 합 K원이 되도록해야한다. 
• 각각의 동전은 몇개라도 사용할 수 있다. 출력: 경우의 수
• 동전의 종류를 몇가지 사용하는지에 따라 분류한다.
• (예를들어 3가지면 1가지만 사용했을 경우, 2가지만 사용했을 경우, 3가지를 사용했을 경우를 더한 값이 모든 경우의 수가 된다.)
• 2차원배열을 사용하면 좋겠지만 메모리 문제로 인하여 1차원 배열을 사용하자
• 점화식: dp[j] += dp[j-coins[j]]

n개의 코인의 사용했을 때

코드

import sys

N, K = map(int, sys.stdin.readline().split())

coins = list()
for _ in range(N):
    coins.append(int(sys.stdin.readline()))
coins.sort()

dp = list([0] * (K+1))
dp[0] = 1

for i in range(0, N):
    i_value = coins[i]
    for j in range(i_value, K+1):
        if dp[j-coins[i]] != 0:
            dp[j] += dp[j-coins[i]]

print(dp[len(dp)-1])

 

느낀점

처음에는 단순하게 생각하여 동전의 종류에 K를 맞추기 위해서 힘을 많이썻지만 표로 정리해보는 습관을 키워보는 것이 가장 중요한 것 같다. 그리고 점화식을 어떻게 유도하는지에 따라서 메모리를 얼마나 효율적으로 사용할수 있는지에 대하여 생각하는 계기가 되는 문제이다.