하루일문
[백준] 11047번 동전 0(파이썬) 본문
문제
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
코드
N, K = map(int, input().split())
coin = [int(input()) for _ in range(N)]
cnt = 0
for i in range(N - 1, -1, -1):
if K // coin[i] > 0:
cnt += K // coin[i]
K = K % coin[i]
if K == 0:
break
print(cnt)해설
가장 큰 수부터 하나하나 넣는 방식인 그리디방법으로 풀어보았다.
다 돌기전에 k == 0인 것을 생각해서 0이면 break로 끝내주었다.
레인지 범위는 거꾸로 돌기때문에 0까지 돌려면 -1인 것을 유의해야할 것같다.
'algorithm > baekjoon' 카테고리의 다른 글
| [백준] 18111번 마인크래프트(파이썬) (0) | 2023.03.28 |
|---|---|
| [백준] 14889번 스타트와 링크(파이썬) (0) | 2023.03.27 |
| [백준] 5014번 스타트링크 (파이썬) (0) | 2023.03.25 |
| [백준] 1914번 하노이 탑 (파이썬) (1) | 2023.03.24 |
| [백준] 10026번 적녹색약 (파이썬) (0) | 2023.03.22 |