알고리즘 | 효율적인 화폐 구성
접근
이 문제를 보고 처음에는 저번에 풀었던 거스름돈 문제랑 비슷하다고 느꼈다. 그떄는 그리디로 풀었던 기억이 있어서 우선 그리디로 접근해보았다.
시도
def try_1():
n, m = map(int, input().split())
coins = []
for _ in range(n):
coins.append(int(sys.stdin.readline().rstrip()))
coins.sort(reverse=True)
count = 0
for i in coins:
count += m // i
m = m % i
if m == 0:
return count
return -1
예시에 나온 테스트케이스는 답이 맞아서 일단 해설을 보기로 했지만 뭔가 조건이 부족하다는 느낌이 강하게 들었다. 그래도 일단은 해설을 보면서 배우기로 했다.
해설
def solution():
n, m = map(int, input().split())
coins = []
for _ in range(n):
coins.append(int(sys.stdin.readline().rstrip()))
d = [10001] * (m + 1)
for i in coins:
d[0] = 0
for j in range(i, m + 1):
if d[j - i] != 10001:
d[j] = min(d[j], d[j - i] + 1)
if d[m] == 10001:
print(-1)
else:
print(d[m])
def solution():
n, m = map(int, input().split())
coins = []
for _ in range(n):
coins.append(int(sys.stdin.readline().rstrip()))
d = [10001] * (m + 1)
for i in coins:
d[0] = 0
for j in range(i, m + 1):
if d[j - i] != 10001:
d[j] = min(d[j], d[j - i] + 1)
if d[m] == 10001:
print(-1)
else:
print(d[m])
역시나 제출했던 코드는 틀렸었다. 단순히 그리디로 접근하는 문제가 아니였다. 이 문제도 다이나믹 프로그래밍으로 푸는 문제였는데 우선 m 의 크기만큼 배열을 선언했고 그 사이에 있는 모든 금액에 대한 최소 화폐를 넣기 위해서 우선 올 수 있는 가장 큰 값인 10000 보다 높은 10001을 배열 안에 전부 넣어주었고 앞으로 오는 값을 넣어주고 min 으로 비교하여 최소값을 넣는 방식으로 진행된다.
내가 해설을 한번 간단하게 보고 스스로 다시 짜보았지만 틀렸었는데 그 이유는 놓친점이 몇가지 있어서였다. 처음에는 단순히 동전의 배수 만큼(예를 들어서 2원 동전이 오면 2, 4, 6, 8..) 이런식으로 값을 1씩 늘려서 넣어주면 끝나는 줄 알았다. 하지만 만약에 동전이 (2, 3, 5) 이렇게 있으면 7 에는 아무 값도 안들어가는 경우가 생겼다.
따라서 이를 해결하기 위해서는 주어진 동전의 값부터 m 값 까지 도는 반복문을 넣어줘야 한다. 예를 들어서 2원 동전이 오면 2원부터 m 원까지, 5원 동전이 오면 5원 부터 m 원 까지.. 이렇게 반복문을 돌면서 확인하는 값을 j 라고 하면 만약 d[j - coin]의 값이 10001 이 아니면(즉, 값이 들어간 적이 있으면) d[j] = min(d[j], d[j - coin] + 1)울 해주는 방식이다.
이렇게 하면 동전으로 만들 수 있는 모든 경우의 수에 값이 들어가게 된다.
Author And Source
이 문제에 관하여(알고리즘 | 효율적인 화폐 구성), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jhon3242/알고리즘-효율적인-화폐-구성저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)