반응형
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에 더하게 되므로 모든 원소를 나누면서 더한것같다.
반응형
'⚙️ 알고리즘 > 백준' 카테고리의 다른 글
[Swift] 백준 10610 - 30 (0) | 2023.01.26 |
---|---|
[Swift] 백준 2895 - 대회 or 인턴 (0) | 2023.01.26 |
[백준/파이썬] 2869 - 달팽이는 올라가고싶다 (0) | 2021.04.25 |
[백준] 2217 - 로프 (다시풀기) (0) | 2021.03.04 |
[백준] 11399 - ATM (0) | 2021.03.04 |