[algorithm] 백준 11047 - 동전 0

[algorithm] 백준 11047 - 동전 0

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 11047번 문제 - 동전 0 의 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다 함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 11047

 

백준 11047번 동전 0 문제 보러가기

 

반응형

 

문제 해석

 

문제에서 주어지는 입력값은 동전의 개수와 만들어야 하는 가격 그리고 동전들의 가치입니다.

이를 이용해 특정 가격을 만드는데 들어가는 최소의 동전 개수를 출력하는 것이 문제의 정답입니다.

힌트 : 문제의 조건을 살펴보면 가격이 큰 동전의 가격은 작은 동전의 가격의 배수임을 확인할 수 있습니다.

 

풀이

 

# 11047 동전 0

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

coin_list = [int(input()) for _ in range(N)]
coin_list.sort(reverse=True)

for coin in coin_list:
    if K >= coin:
        coin_cnt += K // coin 
        K %= coin 
        if K <= 0:
       		break
     
print(coin_cnt)

 

풀이 해석 및 팁

 

문제는 오름차순으로 정렬된 동전의 가격을 입력값으로 주기 때문에 입력받은 뒤 내림차순으로 정렬해 줍니다.

그 후에 가격이 큰 동전부터 원하는 가격에 몇 개나 들어갈 수 있는지를 체크한 다음

몇 개의 동전을 사용해 가격을 낮췄는지를 체크하기 위해 coin_cnt에 더해주고 

그 나머지 가격을 맞춰야 할 가격으로 바꿔준 뒤 다음으로 큰 동전으로 위 과정을 반복합니다.

반복문을 진행하는 도중에 맞춰야할 가격의 값이 0이 되면 반복문을 즉시 중단하고 동전의 개수를 출력해 줍니다.

---

여기까지 백준 11047번 최대 힙 문제 풀이였습니다.

이번 문제의 정답률은 52% 정도입니다.

 

궁금하신 점은 댓글로 남겨주시기 바랍니다.

 

감사합니다.