백준 11047번: 동전 0 - Python 풀이

오늘의 문제

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

 

몇 년 만에 파이썬으로 풀어봤습니다. 그래서 아주 쉬운 문제로...

진짜 input() 빼고 다 까먹어서 문법 검색하며 풀었습니다.

 

내 풀이

N, K = map(int, input().split())

Ai = []
answer = 0

for i in range(0, N):
    Ai.append(int(input()))

Ai.reverse() # 오름차순 -> 내림차순으로 변경

for a in Ai:
    if K == 0: # 0이면 끝
        break
    if a <= K: # K보다 작거나 같은 동전만 취급
        answer += K // a # 몫만큼 개수 카운트
        K %= a # 나머지만 가지고 다음 턴으로

print(answer)

 

쉽지만 간단히 설명을 붙이자면

해당 문제는 그리디 알고리즘으로 분류되어 있는데, 

# 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

# -> 동전 개수가 최소가 되려면 최대한 가치가 큰 동전을 많이 사용해야겠다는 걸 알 수 있음.

뭐 이 부분 때문에 그러지 않나 싶습니다. 

 

동전 개수를 최소로 만들기 위해 현재 가장 가치가 높은 동전을 우선 선택합니다. 그러기 위해 reverse 함수를 통해 오름차순으로 입력받은 값을 다시 내림차로 바꿔서 풀었습니다.

 

파이썬으로도 금세 다시 잘할 수 있게 응원해주십쇼.

감사합니다!