파이썬 백준 11047번
실버4
https://www.acmicpc.net/problem/11047
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
문제 보기

분류 그리디 알고리즘
문제 풀기
처음 접근은 어렵지 않았다. 하지만 한 번 더 생각해 보지 않았던 순간이 "시간초과" 를 한번 내뱉게 하였다.
일단, 문제에서 주어진 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
을 나중에 입력해 보고 얼마나 느린 코드인지 느껴보았다.
'공부하기 > 백준' 카테고리의 다른 글
[Python] 백준 풀기 1541 - 잃어버린 괄호 (0) | 2022.10.09 |
---|---|
[Python] 백준 풀기 1931 - 회의실 배정 (0) | 2022.10.07 |
[Python] 백준 풀기 2231 - 분해합 (2) | 2022.10.05 |
[Python] 백준 풀기 2559 - 수열 (0) | 2022.10.04 |
[Python] 백준 풀기 1904 - 01타일 (2) | 2022.09.30 |