[백준 11047번 동전 0] 문제 해설 - 파이썬

[백준 11047번 동전 0] 문제 해설 - 파이썬

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

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

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

---

문제 접근법

• 이런 문제와 비슷한 문제가 이름만 들으면 알법한 19년 하반기 모 기업의 코딩테스트 문제로 나왔습니다. 쉬운 문제라고 넘어가야할 것이 아닌 정확하고 빠르게 풀어나가는 것이 중요할 것입니다.
• 동전의 갯수 최솟값을 찾는 것이 목표입니다. 따라서 가장 높은 가치를 갖는 동전 부터 차례로 지불 할 수 있는지 확인해야할 것입니다.
• 이를 위해서 파이썬 배열 내장 한수인 sort() 함수를 이용해서 지불할 수 있는 동전의 종류를 높은 가격 순으로 정렬했습니다. sort()함수는 'O(NlogN)으로 정렬합니다.

파이썬 코드

def solution(inputPriceArr):
    global Price
    answer = 0
    for i in range(InputLen):
        if Price // inputPriceArr[i] > 0:
            answer += (Price // inputPriceArr[i])
            Price -= inputPriceArr[i] * (Price // inputPriceArr[i])

    return answer


InputLen, Price= map(int, input().split())
inputPriceArr = []
for i in range(InputLen):
    inputPriceArr.append(int(input()))

inputPriceArr.sort(reverse=True)
print(solution(inputPriceArr))