[BOJ/python] 2293: 동전 1

문제

✔️ gold 4

문제 흐름

동전을 사용해 특정 금액을 만드는 경우의 수를 구하는 문제였다.
일정한 조건이 주어지고 특정 값에 대한 결과값을 찾는다는 점에서 DP를 생각해볼 수 있다.

처음에는 "i번째 값의 동전의 수"를 기준으로 규칙을 찾아보고자 했다.
메모의 차원도 커지고 규칙을 뭐라 특정하기 어려워서 고민하다가 힌트를 얻고 방향을 바꾸게 되었다.
memo[i]를 "i원을 만드는 경우의 수"로 놓는 것이다.

위 그림을 통해 그 규칙을 찾는 과정을 알 수 있다.
1번째 동전만을 이용해 만들 수 있는 경우의 수를 1부터 k까지의 i원을 만드는 경우의 수에 대해 계산한다.
2번째 동전을 추가해 다시 1부터 k까지의 i원을 만드는 경우의 수를 계산하는데,
만약 i가 2번째 동전 값 c보다 큰 경우 i = c + remain이라고 가정할 수 있다.
이 remain은 특정 값이 될테고, 그 값을 만드는 경우의 수는 앞에서 계산한 케이스에 2번째 동전을 붙인 케이스가 된다.

이렇게 누적해서 마지막 동전까지 계산하면 앞에서 구한 경우의 수들을 이용해 규칙적으로 값을 구해나갈 수 있다.
참고로 위 이미지에 초기값: memo[0] = 0이라고 적혀있는데.,, 아무 동전도 안 쓰는 케이스가 있으니 1로 해주는게 맞다.

코드

# 동전 1

import sys
input = sys.stdin.readline

def dp(coins: list, k: int):
    n = len(coins)
    memo = [0 for i in range(k + 1)] # i원을 만드는 경우의 수
    memo[0] = 1

    for coin in coins:
        for i in range(1, k + 1):
            if i - coin >= 0:
                memo[i] += memo[i - coin]

    # print(* memo)
    return memo[-1]

if __name__ == "__main__":
    n, k = map(int, input().split())

    coins = []
    for i in range(n):
        coins.append( int(input()) )
    
    result = dp(coins, k)
    print(result)