백준 12865번 python 풀이 - 동전 0

문제 링크

12865번

해결책

import sys

INF = 999999999

N, K = map(int, sys.stdin.readline().split())

coins = []

for _ in range(N):
    temp = int(sys.stdin.readline())
    if temp < K:
        coins.append(temp)
    elif temp == K:
        print(1)
        exit()

"""
DP를 활용한 풀이. 조금 당연하게도, Memory 초과가 발생한다.

dp = [INF for i in range(K + 1)]
dp[0] = 0

for coin in coins:
    for idx in range(coin, K+1):
        dp[idx] = min(dp[idx], dp[idx-coin] + 1)


print(dp[-1])
"""

# 그리디 알고리즘을 활용한 풀이
# 먼저, coins는 모두 첫번째 coin의 배수이므로, 결과도 coin들도 싹 a1으로 나눠버릴까?
# 굳이 의미가 있나? 큰 수의 계산을 작은 수의 계산으로 바꾸는게 효율적인가?

# divider = coins[0]
# if divider != 1:
#     for i in range(0, len(coins)):
#         coins[i] //= divider
#
#     K //= divider

# 여기서 DP를 쓸수도 있지 않을까?
# 근데 최소가 1이면 그대로겠네.


# 그리디 아이디어
# 먼저, 제일 큰 동전을 사용해서 값을 구한다.
# 그 나머지를 아래의 동전들로 구하려고 해본다.
# 동전의 처음까지 내려왔다면, 위의 동전의 갯수를 줄여본다.


cur_idx = len(coins) - 1
_sum = 0
remain = K
cur_val = coins[-1]
while remain != 0:
    if cur_val <= remain:
        cur_num = remain // cur_val
        remain = remain - cur_num * cur_val
        _sum += cur_num
    cur_idx -= 1
    if cur_idx < 0:
        break
    cur_val = coins[cur_idx]

if remain == 0:
    print(_sum)
    exit()

주석으로 달 설명

그리디 쉬운 문제. dp적인 접근도 생각나서, 시도해 보았지만 조금 당연할지도 모르지만 시간초과가 났다.