728x90
난이도 : 실버4
풀이일 : 05011
https://www.acmicpc.net/problem/11047
링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐
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 재할당을 먼저했다가 한 번 더 틀림
꼼꼼하게 문제를 읽고 코딩하자
'알고리즘 > 🥈 실버' 카테고리의 다른 글
백준 2164 카드2 자바 풀이 (0) | 2023.07.06 |
---|---|
백준 1158 요세푸스 문제 자바 풀이 (0) | 2023.07.03 |
백준 1463 1로 만들기 파이썬 풀이 (0) | 2023.05.01 |
백준 1991 트리 순회 파이썬 풀이 (0) | 2023.04.29 |
백준 1697 숨바꼭질 파이썬 풀이, 반례 (0) | 2023.04.23 |