본문 바로가기

알고리즘/🥈 실버

백준 11047 동전 0 파이썬 풀이

728x90

난이도 : 실버4

풀이일 : 05011

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


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


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 재할당을 먼저했다가 한 번 더 틀림

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