개발/algorithm
[백준 2292번] 동전1 -python
zzi_on2
2022. 1. 27. 13:17
문제 링크
https://www.acmicpc.net/problem/2293
2293번: 동전 1
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
www.acmicpc.net
풀이
- 프로그래머스의 거스름돈 문제와 비슷한 것 같다
[프로그래머스][level3] 거스름돈 -python
문제 링크 https://programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름..
zzion2.tistory.com
- answer[]은 인덱스에 해당하는 가격을 동전들로 만들 수 있는 경우의 수
- 점화식 : answer[price] += answer[price-coin]
n, k = map(int,input().split())
coins = []
# 각 인덱스에 해당하는 가격을 동전들로 만들 수 있는 경우의 수
answer = [0] * (k+1)
answer[0] = 1
for _ in range(n):
coins.append(int(input()))
for coin in coins:
for price in range(coin, k+1):
answer[price] += answer[price-coin]
# k를 만들 수 있는 경우의 수
print(answer[k])