백준 11047 동전 0

❌ 백준 11047 동전 0

오답.

그리디 알고리즘으로 분류되어있지만 단순하게 풀었다.

1) 받은 동전값들을 배열에 넣는다.

2) 높은 값부터 차례대로 K와 비교한다.

3) K보다 작거나 같으면 K를 동전값으로 나눠서 몫을 result에 더하고, 나머지를 다시 K로 넣고 돌린다.

4) K가 0이면 break.

처음엔 동전값과 K가 같은 경우를 고려하지 않아서 실패했다.

2 5000
2500 5000
을 넣으니 1이 나와야 될게 2가 나왔다.

그제야 깨달았다.

import sys

n,k = map(int,sys.stdin.readline().rstrip().split())

num_arr = []
result = 0

for i in range(n) :
    num_arr.append(int(sys.stdin.readline()))

for i in range(n-1,-1,-1) :
    if num_arr[i] <= k :
        result += k // num_arr[i]
        k %= num_arr[i]
        if k == 0 :
            break

print(result)