[파이썬] 백준 11047번 동전 0

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

11047번: 동전 0

 

[문제 이해]

입력 받은 동전 종류 중 일부를 적절히 사용해서 입력 받은 결과 값을 만들기 위해 필요한 최소 동전 개수를 구하는 문제이다. 

 

[문제 풀이]

내림차순 정렬을 통해 가지고 있는 동전 중 가장 높은 수부터 만들어야 하는 값과 비교한다. 가지고 있는 동전이 크다면 더 작은 동전과 비교해가며 동전의 개수를 센다. 이때 동전의 개수는 몫 연산자를 사용하여 구할 수 있고, 남은 나머지 금액은 나머지 연산자를 통해 구할 수 있기 때문에 어렵지 않게 문제를 해결할 수 있었다.

# 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
# 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

import sys
N, K= map(int, sys.stdin.readline().split()) # 동전 종류의 수, 만들 금액
A = list() # 동전 종류

for i in range(N):
    A.append(int(sys.stdin.readline()))

A.sort(reverse = True) # 내림차순 정렬

sum = 0 # 동전 개수

for i in A:
    if K < i: # 동전이 만들 금액보다 크다면 스킵
        continue
    else:
        sum += (K // i)
        K %= i

print(sum)

 

+ 가끔 문제를 풀 때 시간 초과가 뜨기도 하여 input() 대신 sys.stdin.readline()을 사용하여 입력을 받는데 이 때문에 입력 받는 값의 형태에 따라 split() 함수의 사용 여부가 헷갈리기도 한다. split()은 문자열을 쪼개는 함수라는 것을 기억하자!

 

split()

split() 함수는 문자열을 쪼개는 함수로, 문자열을 특정 구분자를 기준으로 나누는 함수이다.

https://docs.python.org/ko/3/library/stdtypes.html#str.split

Built-in Types

str.split(sep=None, maxsplit=-1)

sep을 구분자 문자열로 사용하여 문자열에 있는 단어들의 리스트를 돌려준다. maxsplit 이 주어지면 최대 maxsplit 번의 분할이 수행된다 (리스트는 최대 maxsplit+1 개의 요소).