[Python] 백준 풀기 11047 - 동전 0

파이썬 백준 11047번

실버4

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

11047번: 동전 0

 

 

 

문제 보기

분류 그리디 알고리즘

 

 

 

문제 풀기

처음 접근은 어렵지 않았다. 하지만 한 번 더 생각해 보지 않았던 순간이 "시간초과" 를 한번 내뱉게 하였다.

일단, 문제에서 주어진 N 과 K 를 입력받고, 동전의 종류를 리스트에 하나하나 저장하여 초기 세팅을 한다.

처음에 생각한 방법은 K 를 만들 수 있는 가장 작은 동전의 개수를 구해야 하기 때문에 가장 큰 수를 갖는 동전을 입력하여 K 와 비교해 보고 K 를 줄여나가는 방법이었다. 하지만 이 방법은 K 가 매우 커지고 N 이 매우 작아질 때 시간 초과를 불러일으킨다. 이 방법을 생각하는 과정에서 K 를 동전 값으로 나누어 몫으로 따져보면 어떨까 싶은 게 스쳐 지나가긴 했는데.. 한번 틀리고서야 방법이 잘못되었음을 알았다.

"시간초과" 를 맛본 후, K 를 가장 큰 동전으로 나누어 몫이 발생한다면 count += K // coins_ls[-1] 이 코드로 그 몫을 동전의 개수에 추가시켜 주고, 몫이 발생하지 않는다면 coins_ls.pop() 로 제거하여 다음으로 큰 동전의 값을 대입하는 방법의 코드를 작성하였다. 그리고, 이 루프를 돌면서 K 는 K %= coins_ls[-1] 로 현재 가장 큰 동전 값으로 나누어진 나머지를 다시 받아 저장하는 식으로 진행된다.

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

N, K = map(int, inputdata().split())
coins_ls = []

for _ in range(N):
    coin = int(inputdata().strip())
    coins_ls.append(coin)

# print(coins_ls)         #

count = 0
while K > 0:
    if K < coins_ls[-1]:
        coins_ls.pop()
        # print(f'coins_ls: {coins_ls}')          #
    else:
        count += K // coins_ls[-1]
        K %= coins_ls[-1]
    # print(f'K: {K}')            #

print(count)

 

 

 

추가 하기

처음에 작성한 시간초과 코드

import sys
inputdata = sys.stdin.readline

N, K = map(int, inputdata().split())
coins_ls = []

for _ in range(N):
    coin = int(inputdata().strip())
    coins_ls.append(coin)

print(coins_ls)         #

count = 0
while K > 0:
    if K < coins_ls[-1]:
        coins_ls.pop()
        print(f'coins_ls: {coins_ls}')          #
    else:
        K = K - coins_ls[-1]
        count += 1
    print(f'K: {K}')            #

print(count)



# 10 4790
# 1
# 5
# 10
# 50
# 100
# 500
# 1000
# 5000
# 10000
# 50000

# [1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]
# coins_ls: [1, 5, 10, 50, 100, 500, 1000, 5000, 10000]
# K: 4790
# coins_ls: [1, 5, 10, 50, 100, 500, 1000, 5000]
# K: 4790
# coins_ls: [1, 5, 10, 50, 100, 500, 1000]
# K: 4790
# K: 3790
# K: 2790
# K: 1790
# K: 790
# coins_ls: [1, 5, 10, 50, 100, 500]
# K: 790
# K: 290
# coins_ls: [1, 5, 10, 50, 100]
# K: 290
# K: 190
# K: 90
# coins_ls: [1, 5, 10, 50]
# K: 90
# K: 40
# coins_ls: [1, 5, 10]
# K: 40
# K: 30
# K: 20
# K: 10
# K: 0
# 12

이 코드로 답안을 제출하니 0 ~ 60 % 가량 linear 하게 올라가다가 그 뒤 음의 가속도가 붙은 거 마냥 점점 느려지더니 71 % 를 겨우 넘어서고 72 % 가 되니까 완전히 멈춰버렸다. 그러고 숨 막히는 몇 초가 지난 뒤 "시간초과" 출력 받음.

예제로

1 1,000,000

1

을 나중에 입력해 보고 얼마나 느린 코드인지 느껴보았다.