⚙️ 알고리즘/백준
[백준] 11047 - 동전 0
dev_zoe
2021. 3. 4. 02:54
반응형
1차 풀이)
직관적으로 생각했을 때 4200을 1000으로 나누고 그다음 100으로 나누게 되면 4+2 = 6번이 된다.
4790은 1000으로 4번 나누고 500으로 1번 100으로 2번 50으로 1번 10으로 4번 총 12번이 된다.
그럼 5000부터는 몫이 0이 되니까 이때 멈추고 그 전까지로 반복문을 돌려서 차례대로 나누어가면서
나누어 떨어지는 횟수만 더하면 정답이 되지 않을까?!
N, K = map(int, input().split())
coins = list(int(input()) for _ in range(N))
result = 0
for i in range(len(coins)):
if int(K/coins[i])==0:
break
# 나누어 떨어지는 가장 큰수부터 나누기
for j in range(i, -1, -1):
if K==0:
break
result+=K//coins[j]
K = K%coins[j]
print(result)
다른사람 풀이
N, K = map(int, input().split())
Coins = []
for i in range(N) : Coins.append(int(input()))
ans = 0
while K > 0 :
coin = Coins.pop()
ans += K // coin
K %= coin
print(ans)
pop() -> 맨 뒤부터 처리하게되므로 큰수부터 나누게됨
어차피 K보다 큰 수로 나누어도 0을 ans에 더하게 되므로 모든 원소를 나누면서 더한것같다.
반응형