[BOJ/python] 11047번 동전 0

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

11047번: 동전 0

문제 해석

 

동전의 갯수와 구할 돈의 양을 입력 받은 후 동전의 가치를 차례대로 입력받는다.

그 후 동전을 사용하여 k값을 만든 최소한의 동전의 양을 구하는 문제이다.

 

---

코드

input = __import__('sys').stdin.readline
n, k = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(int(input()))
arr = arr[::-1]

ans = 0
i = 0

while k:
    if k < arr[i]: i += 1
    else:
        ans += k // arr[i]
        k %= arr[i]
        i += 1
print(ans)

---

문제 풀이

 

먼저 가장 큰 가치의 동전부터 시작하여

동전의 가치만큼 나누어 ans 값에 더해주고

나누고 남은 값을 다시 k 값에 저장한 후 다시 k값을 다음 동전의 가치만큼 나누어 ans 값을 더해준다.이를 반복하면 결국 가장 최소로 사용하는 동전의 갯수를 구할 수 있다.

 

따라서 동전의 가치를 차례로 입력받은 후 이 배열을 거꾸로 뒤집은 후 반복문을 사용하여 차례로위의 알고리즘을 반복해 주어 문제를 해결했다.

 

원문

https://ddingmin00.tistory.com/23

[BOJ/python] 11047번 동전 0