[백준] 11047 - 동전 0

www.acmicpc.net/problem/11047

11047번: 동전 0

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에 더하게 되므로 모든 원소를 나누면서 더한것같다.