(Python)백준 코딩테스트 연습 - 동전 0(11047)

1. 문제

https://www.acmicpc.net/problem/11047

11047번: 동전 0

2. 풀이

import sys

# n : 돈 종류의 개수, k : 목표 가치
n, k = map(int, sys.stdin.readline().split())

# m_list : 돈의 종류
m_list = []
for i in range(n):
    m_list.append(int(sys.stdin.readline()))

# m_cnt : 돈 개수 최솟값    
m_cnt = 0
for i in m_list[::-1]:
    if k == 0:
        break
    p_cnt = k // i
    m_cnt += p_cnt
    k -= i * p_cnt
print(m_cnt)

3. 후기

 - 이 문제는 실버 5단계의 문제로는 더이상 2점밖에 주지 않아 실버 4단계로 올라가 풀게된 첫 문제입니다(쉬운 문제라 그런지 실버 4단계임에도 3점 밖에는 주지 않았습니다...). 방식은 그리디 알고리즘을 이용하여 해결하였고, 최소 개수를 구하기 위해서는 가장 큰 액수의 돈부터 확인하여 가장 작은 액수의 돈까지 개수를 확인하는 방법을 사용하였습니다.