파이썬 알고리즘
[파이썬] 백준 11047 동전 0
뜻 지, 깨달음 오
2022. 12. 6. 18:40
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
걸리는 시간은 똑같지만 코드 길이를 줄여봤다
일단 거스름돈 배열을 만들고,
가장 뒤부터 배열을 순회하면서 거스름돈이 나누어지는 만큼 cnt에 더한다.
<처음 풀이>
N, K = map(int, input().split())
money = []
for i in range(N):
temp = int(input())
money.append(temp)
# print(money)
cnt = 0
while K>0:
for i in range(N-1, -1, -1):
if K//money[i] == 0:
continue
elif K//money[i] > 0:
cnt += K//money[i]
K = K % money[i]
print(cnt)
<최종 코드>
N, K = map(int, input().split())
money = []
for i in range(N):
temp = int(input())
money.append(temp)
cnt = 0
while K:
for i in range(N-1, -1, -1):
if K//money[i] > 0:
cnt += K//money[i]
K = K % money[i]
print(cnt)