[Python] 백준 11047번_동전 0

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

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원을 만드는데 필요한 동전 개수의 최솟값을 출력
• 시간 제한: 1초
• 메모리 제한: 256 MB

 

"""
입출력 예시)

(예제 입력 1) 
10 4200
1
5
10
50
100
500
1000
5000
10000
50000
    -> 6

(예제 입력 2)
10 4790
1
5
10
50
100
500
1000
5000
10000
50000
    -> 12
"""

 

 

## 의사코드 ##

# 동전 개수를 최소로 -> 가장 큰 가치를 가진 동전부터 차감

# 동전의 가치를 큰 값부터 내림차순 정렬
# coins.sort(reverse=True)

# cnt = 0 # 동전의 개수
# for c in coins:
#     # 동전의 가치가 k보다 큰 경우, 그냥 통과
#     if c > k:
#         continue 
#     else:
#         # 동전의 개수 + k를 동전으로 나눈 몫
#         cnt += k // c
#         # 남은 k = k를 동전으로 나눈 나머지
#         k %= c

 

 

 

통과한 코드

 

n, k = map(int, input().split())
coins = [] # 동전의 가치를 담을 리스트
for _ in range(n):
    coin = int(input())
    coins.append(coin)

# 동전의 가치를 큰 값부터 내림차순 정렬
coins.sort(reverse=True)

# 동전의 개수
cnt = 0
for c in coins:
    # 동전의 가치가 k보다 큰 경우, 그냥 통과
    if c > k:
        continue 
    else:
        # 동전의 개수 + k를 동전으로 나눈 몫
        cnt += k // c
        # 남은 k = k를 동전으로 나눈 나머지
        k %= c
print(cnt)

 

 

 

 

 

비슷한 문제

 

https://monzheld.tistory.com/162#3.%20%EB%B9%84%EC%8A%B7%ED%95%9C%20%EB%AC%B8%EC%A0%9C

[Python] 백준 브론즈3_세탁소 사장 동혁

 

https://monzheld.tistory.com/128#2.%20%EB%8B%A4%EB%A5%B8%20%ED%92%80%EC%9D%B4

[Python] 백준 브론즈2_거스름돈