백준 2293 동전1

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/2293

풀이

난이도 : Gold V

이 문제는 전형적인 dp(dynamic programming) 문제로 주어진 동전을 가지고 정해진 k값을 만드는 문제이다.
조금 주의해야 될 점이라면 동전이 중복되서 여러번 사용될 수 있다는 점이다.

1) 주어진 동전들을 입력받으면서 k보다 큰 동전은 필요없으므로 k보다 큰 동전을 제외하고 입력받는다.
2) dp 테이블을 만든다.
3) coin들을 하나씩 살펴보면서 coin을 하나 사용했을 경우를 생각하여 dp[coin]을 1 추가시켜준다.
4) 해당 coin 다음칸부터 k까지 이 coin만 사용했을 경우를 생각하여 dp의 값을 추가시켜준다.
5) dp[k]를 출력한다.

👉 bottom에서부터 모든 coin에 해당하는 값들을 추가시켜주면 3 = 1 + 2 or 3 = 2 + 1 처럼 중복되는 경우가 발생하므로 각 coin만 사용했을 경우로 나누어서 dp값을 coin의 개수만큼 변경해주어야한다.

코드

n, k = map(int, input().split())

coins = []
dp = [0] * 10001

for _ in range(n):
    coin = int(input())
    if coin > k:
        continue
    coins.append(coin)

for coin in coins:
    dp[coin] = dp[coin] + 1
    for i in range(coin+1, k+1):
        dp[i] = dp[i] + dp[i-coin]

print(dp[k])