Hikenny25
11047 - 동전 0 본문
https://www.acmicpc.net/problem/11047
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
- Greedy
import sys
input = sys.stdin.readline
n,k = map(int, input().split())
a = list()
for _ in range(n):
a.append(int(input()))
cnt = 0
while n >= 0:
coin = a[n-1]
cnt += (k // coin)
k -= (coin * (k//coin))
n -= 1
print(cnt)동전이 배수 관계라면 그리디 알고리즘으로 구한 최적해가 최솟값이니까
기본 그리디로 구현했다!
가장 큰 동전부터 작은 동전까지 내려가면서 계산하면 된다.
'baekjoon (solved.ac) > class 3 Solve' 카테고리의 다른 글
| 17219 - 비밀번호 찾기 (1) | 2022.10.25 |
|---|---|
| 11399 - ATM (0) | 2022.10.25 |
| 1764 - 듣보잡 (0) | 2022.10.25 |
| 1620 - 나는야 포켓몬 마스터 이다솜 (0) | 2022.10.25 |
| 1676 - 팩토리얼 0의 개수 (0) | 2022.10.25 |
Comments