[백준/파이썬] 11047 동전 0 - 그리디

소스 코드 1

n, k = map(int, input().split())

coin_types = []
for i in range(n):
    coin = int(input())
    coin_types.append(coin)

coin_types.sort(reverse=True) # 내림차순으로 정렬

count = 0
for coin in coin_types:
    if coin <= k:
        count += k//coin
        k -= k//coin * coin

print(count)

• 동전을 최소의 개수로 사용해야 하므로 K보다는 작은 동전들 중 가장 금액이 큰 동전을 최대의 개수로 사용해야 함
• 동전 종류를 내림차순으로 정렬해서 금액이 큰 동전들부터 순서대로 비교

소스 코드 2

import sys
n, k = map(int, sys.stdin.readline().split())

coin_types = [int(sys.stdin.readline()) for _ in range(n)]
coin_types.sort(reverse=True)

count = 0
for coin in coin_types:
    if coin <= k:
        count += k//coin
        k -= k//coin * coin

print(count)

• 여러줄 입력받는 코드를 간결하게

주요 개념

• 반복적인 작업을 해야 하는 경우  map()  함수를 사용
  •  map(함수, literable data) 
  • 보통 여러 개의 데이터를 담고 있는 리스트나 튜플이 map의 두 번째 인자로 옴

• 시간 초과를 방지하기 위해  input()  대신  sys.stdin.readline()  사용
• 내림차순 정렬할 때  sort 안에 매개변수  reverse=True  이용 (기본값은  reverse=False )
• 숫자 여러 개를 여러 줄에 입력받아 리스트에 저장

coin_types = [int(input()) for _ in range(n)]

 

Reference

• 파이썬 입력받기
• map 함수