[실버 4] 11047번: 동전 0

Original Source: 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는 A(i-1)의 배수)

출력

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

---

사고의 흐름

• 가치가 K가 넘는 동전은 하나도 쓸 필요가 없으니, Input을 받을 때 가치가 K 이하인 동전만 받으면 되겠다.
• 'A1 = 1, i ≥ 2인 경우에 Ai는 A(i-1)의 배수'이니까 가치가 큰 동전을 우선적으로 선택하면 무조건 최적해를 구할 수 있네. 전형적인 그리디 알고리즘의 예시다.
• Input을 반복문 + sys.stdin.readline()으로 받을 때 들어온 Input이 가치가 K 초과인지 확인하고 리스트에 저장하기가 번거롭겠네. 왜냐하면 조건문에서 Input과 K값을 비교하고, 다시 Input을 리스트에 넣어야 하니까 Input을 임시 변수에 저장해놓아야 하거든.
• 조건문을 사용하지 않고 다른 메서드를 이용하는 방법은 없을까?
• 잘 모르겠다...그냥 다 받은 다음 리스트 컴프리헨션을 이용해서 K 초과 원소를 다 지워버리는 방법이 편해 보인다.

 

• 작성한 로직 자체는 맞는 것 같은데, 시간 초과가 뜬다. N이 10밖에 안 되니까 이중 반복문 써도 되겠지? 라고 안일하게 생각했는데, K의 범위가 100,000,000이었다. 문제를 자세히 읽고 특히 변수의 범위에 신경쓰자.
• 반복문을 돌리면서 K의 값을 조작하지 말고, 몫 나누기 연산자를 사용해서 수학적으로 처리하자.

내가 작성한 소스코드

import sys

n, k = map(int, sys.stdin.readline().split())
coins = []
for line in sys.stdin:
    coins.append(int(line.rstrip()))

coins = [item for item in coins if item <= k]

cnt = 0
for coin in reversed(coins):
    if k == 0:
        break

    cnt += (k // coin)
    k -= (coin * (k // coin))

print(cnt)

남이 작성한 소스코드

secrett2633 님:
https://www.acmicpc.net/source/13934478

피드백

• 똑같은 코드를 제출해도 메모리 사용량과 실행 시간에 차이가 날 수 있다. 백준 사이트가 달라져서 그런 건지, 아니면 로컬 환경이 영향을 주는 건지 궁금하다.
• 리스트 컴프리헨션을 사용하면 프로그램 실행 시간이 늘어난다. 반복문을 써서 일일히 append()를 하는 것보다는 빠르지만, 그래도 사용하지 않아도 될 때 굳이 사용하지는 말도록 하자.
• K값을 줄일 때 나머지 연산자를 사용하면 손쉽게 자릿수를 줄일 수 있다.