[백준_2293] 동전 1 python

확실히 dp의 경우 골드와 실버 차이가,

격렬하게 느껴진다,,

 

풀다가 모르겠어서 구글링을 통해 아이디어를 얻었다.

이걸 어케 생각하는거지,,

 

# n, k 입력
n, k = map(int, input().split())

# coin_list
coin_list = []

# coin_list 입력
for _ in range(n):
    coin_list.append(int(input()))

# dp 설계
dp = [
    0 for _ in range(k + 1)
]

# dp 초기설정
dp[0] = 1

# dp 채워넣기
# 코인리스트에서 코인을 하나씩 꺼내서
for coin in coin_list:
    # dp를 돌면서
    for i in range(k + 1):
        # 지금 위치 - 코인 값 만큼이 존재하면,
        if i - coin >= 0:
            # 그 값을 더해줌
            dp[i] += dp[i - coin]

# 출력
print(dp[k])