[백준 11047] 동전 0 - 파이썬

백준 11047

---

 

풀이과정

Think! 그리디 알고리즘에 따라, 최적이라고 생각되는 해를 선택한다. 지불하는 동전의 갯수를 최소로 하려면, 가장 큰 단위의 동전을 우선 사용해야 한다.

 

1) N, K를 입력받는다.

2) N번 동안 동전의 가치를 입력받아, 리스트에 저장한다.

3) for문을 이용하여 오름차순으로 저장된 리스트의 가장 끝 인덱스에 위치한 동전부터 사용한다.

4) 동전의 가치가 남아있는 금액(K)보다 작거나 같을 때, 해당 동전을 사용할 수 있으므로 if 조건문을 걸어준다.

5) 조건을 만족시킨다면, K를 동전 가치로 나눈 몫 만큼 동전 갯수를 추가한다.

6) K를 동전 가치로 나눈 나머지가 남아있는 금액(K)이 된다. 

7) 반복문이 종료되면, 최종 동전 갯수를 출력한다.

 

N, K = map(int, input().split())
coins = []
cnt = 0

# 입력받은 동전 가치를 리스트에 저장
for i in range(N):
    coins.append(int(input()))

# 가장 큰 가치의 동전부터 사용한다.
for j in range(N-1, -1, -1):
    # 남아있는 금액보다 동전의 가치가 작거나 같을 때, 지불 가능
    if K >= coins[j]:
        cnt += K//coins[j]
        K = K%coins[j]

print(cnt)