⚙️ 알고리즘/백준

[백준] 11047 - 동전 0

dev_zoe 2021. 3. 4. 02:54
반응형

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

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

반응형