백준 알고리즘 11047 (동전 0) - python

백준 알고리즘 11047 (동전 0)

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

11047번: 동전 0

 

의외로 시간이 조금 걸렸다.

 

이 문제는 풀이가 간단해지는 전제 조건들이 있다.

 

1. 주어진 동전들로 무조건 조합이 된다 : 예외 처리 없어도 됨

2. 동전은 오름차순으로 입력이 들어온다 : 역순으로만 하면 내림차순

 

따라서, 나름 간단하게 풀이가 가능하다.

 

1. 큰 수부터(역순으로) 목표 K를 나눌 수 있는 만큼 나눈다.

  -> 목표 K보다 큰 값인 경우는 무시

2. 1.의 나머지를 다시 K로 치환.

3. K가 0이 되면 print하고 break.

 

[Code]

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
coins = list(map(int, [input() for _ in range(N)]))
result = 0

for coin in coins[::-1]: # lines 역순 : 큰 수부터
    if K >= coin: # 목표보다 큰 동전은 무시
        result += K // coin # K를 최대값으로 우선 나누고 몫을 누적
        K = K % coin # 나머지만 남김
    if K == 0: # 정답 출력
        print(result)
        break # 정답이면 더이상 진행 안함