2293번: 동전 1 / gold 5 / DP

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

2293번: 동전 1

'''
2293번: 동전 1 / gold 5 / DP
'''
import sys

input = sys.stdin.readline

# n, k, coin_list 입력받기
n, k = map(int, input().split())
coin_list = []
for _ in range(n):
    coin_list.append(int(input()))
# DP 리스트 초기화
dp = [0 for _ in range(k + 1)]
dp[0] = 1
# DP 리스트 갱신하기
for coin in coin_list:
    for value in range(coin, k + 1):
        if value - coin >= 0:
            dp[value] += dp[value - coin]
# 출력하기
print(dp[k])

코드 리뷰

- 해당 문제는 DP 점화식을 30분 안에 찾지 못해서 구글링을 해서 문제를 해결했습니다.

 

- DP 리스트

- dp 리스트를 0~k의 값까지의 범위로 지정합니다. / dp 리스트 인덱스 값 == k의 값의 경우의 수를 넣을 예정

 EX) dp[3] = 2 라고 하면, k=3일때, 2가지 경우의 수가 있다는 뜻

 

- DP 로직

(1) 입력 받은 코인 값들을 하나씩 꺼내기

(2) 꺼낸 코인 값 ~ k 값 까지의 dp리스트를 갱신하기