BOJ_2293 동전 1

n, k = map(int, input().split())
coin = []
for _ in range(n):
    coin.append(int(input()))
dp = [0 for _ in range(k+1)]

dp[0] = 1
for c in coin:
    for i in range(k+1):
        if i - c >= 0:
            dp[i] += dp[i-c]

print(dp[k])

제일 가독성이 좋은 파이썬 코드로 가져와 봤습니다.

배열을 두 개 만들어 줘야 한다.

코드로 예시를 들겠다.

coin[] → 동전의 종류를 넣는 배열

dp[] → 합의 경우의 수를 넣는 배열

dp[n] → 동전의 합이 n인 경우의 수이다.

ex) dp[7] → 동전의 합이 7인 경우의 수

표에는 규칙이 있어요

숫자 1만 사용할떄는 1+1+… +1 = n 이거 하나 밖에 없어요 그래서 모든 수를 1로만 만든다면 한 가지밖에 없어요

숫자 1과 2를 사용할 때부터 규칙이 생깁니다. dp[2] 부터 2가 들어갈 수 있죠.