알고리즘 스터디 - 백준 2294번 : 동전 2
문제 해석
- n가지 종류의 동전을 사용해 가치의 합이 k원이 되도록하지만 동전의 개수가 최소가 되도록함
- 조합으로 구해야 함
입력
- n, k를 입력 받음
- n개의 줄에 동전의 가치가 주어짐
어떤 알고리즘을 사용해야할까?
3 15
1
5
12
0 - 0
1 - 1
2 - 1, 1
3 - 1, 1, 1
4 - 1, 1, 1, 1
5 - 5
6 - 5, 1
7 - 5, 1, 1
8 - 5, 1, 1, 1
dp[0] = 0
dp[1] = dp[1-1] + 1
dp[2] = dp[2-1] + 1
- 이런 형식으로 했을 때 특정 위치에 있는 DP[i] = min(DP[i-coin]) + 1이다.
- 여기서 최솟값은 모든 coin을 순환하면서 값을 계산하고 특정 리스트에 저장한 후 그 리스트의 최솟값을 의미한다.
알고리즘 코드
n, k = map(int, input().split())
coin = []
DP = [0 for _ in range(k + 1)]
for i in range(n):
coin.append(int(input()))
for i in range(1, k + 1):
check = []
# 각 코인을 순환
for j in coin:
# 코인을 순환하면서 불가능하지 않는 경우를 지속적으로 더해나감
if j <= i and DP[i - j] != -1:
check.append(DP[i - j])
# 비어있으면 불가능하다는 의미
if not check:
DP[i] = -1
# 비어 있지 않으면 최소 개수 + 1
else:
DP[i] = min(check) + 1
print(DP[k])
Author And Source
이 문제에 관하여(알고리즘 스터디 - 백준 2294번 : 동전 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@guri_coding/알고리즘-스터디-백준-2294번-동전-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)