백준 11047 동전 0 파이썬 풀이

난이도 : 실버4

풀이일 : 05011

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

11047번: 동전 0

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답 -> 시간초과

# 최초 시도 while 사용 -> 71% 시간초과
# 몫을 먼저 더해주고 K 재할당해야 코인 세기 가능

import sys

N, K = map(int, sys.stdin.readline().split())
coin = [0] * N
count = 0
for i in range(N):
    coin[-i-1] = int(sys.stdin.readline().strip())
    
for i in range(N):
    while K >= coin[i]:
        K -= coin[i]
        count += 1
        
print(count)

코드 구성

• 동전의 종류를 큰 단위부터 거꾸로 입력 받아 배열 저장
• 배열을 순회하며 동전보다 값이 크다면, 크거나 같은 동안 해당 단위 뺄셈

틀린 이유

• 너무 큰 단위에서 동전을 계속 빼는 과정에서 시간초과 발생 추정

---

최종 정답

# 최초 시도 while 사용 -> 71% 시간초과
# 몫을 먼저 더해주고 K 재할당해야 코인 세기 가능

import sys

N, K = map(int, sys.stdin.readline().split())
coin = [0] * N
count = 0
for i in range(N):
    coin[-i-1] = int(sys.stdin.readline().strip())

for i in range(N):
    if K >= coin[i]:
        count += K // coin[i]
        K = K % coin[i]

print(count)

코드 변화

• 동전의 단위보다 주어진 값이 크다면, 나눗셈 활용
• 동전은 나눗셈의 몫 만큼 증가
• 값에는 나눈 나머지 재할당

---

느낀점

K 재할당을 먼저했다가 한 번 더 틀림

꼼꼼하게 문제를 읽고 코딩하자