[파이썬/Python] 백준 14916번: 거스름돈

숨·2024년 7월 4일

코테

알고리즘 문제 풀이

목록 보기

14/105

📌 문제 : 백준 14916번

📌 문제 탐색하기

n : 거스름돈 액수 (1 ≤ n ≤ 100,000)

✅ 입력 조건
1. 거스름돈 액수 입력
✅ 출력 조건
1. 거스름돈의 동전 최소 개수 출력
2. 거슬러 줄 수 없으면 -1 출력

1단계) n이 5의 배수인지 확인하고, 맞다면 몫을 count에 더해주고 종료한다.
2단계) 5의 배수가 아니라면 n이 0이 될 때까지 n에서 2를 계속 빼주면서 그 횟수를 count한다.

위의 2가지 단계를 반복하면서 최소 동전 개수를 구한다.

만약 n에서 2를 뺀 값이 0보다 작으면, 이는 거스름돈을 줄 수 없는 상황이라고 할 수 있으므로 -1을 출력한다.

가능한 시간복잡도

입력받기 → $O(1)$
while루프에서 n이 0 이하가 될 때까지 빼기 → $O(n/2) = O(n)$

최종 시간복잡도
$O(n)$ 으로 제한 시간 내에 연산이 가능하다.

알고리즘 선택

while문으로 반복하면서 거스름돈의 동전 최소 개수 구하기.

📌 코드 설계하기

n을 입력
while 루프 작성
n이 5의 배수인지 확인
아닌 경우 2 빼고 count를 1씩 증가
만약 n이 0보다 작으면 종료 후 -1 출력

📌 시도 회차 수정 사항

1회차

📌 정답 코드

import sys

input = sys.stdin.readline

# 1. n을 입력
n = int(input())

# 2. while 루프 작성
count = 0

while True:
    # 3. n이 5의 배수인지 확인
    if n % 5 == 0:
        count += n//5
        break

    # 4. 아닌 경우 2 빼고 count를 1씩 증가
    else:
        n -= 2
        count += 1

    if n < 0:
        break

# 5. 만약 n이 0보다 작으면 종료 후 -1 출력
if n < 0:
    print(-1)
else:
    print(count)

결과

📌 회고

while True:
    # 3. n이 5의 배수인지 확인
    if n % 5 == 0:
        count += n//5
        break

    # 4. 아닌 경우 2 빼고 count를 1씩 증가
    else:
        n -= 2
        count += 1

    if n < 0:
        print(-1)
        break

print(count)

중간 코드에 if문을 위와 같이 작성했더니, 거스름돈을 줄 수 없는 경우에 -1과 계산 과정에서 얻은 count값이 함께 출력되었다.
예제에 있는 것은 잘 수행되었지만 반례를 확인해보지 않았다면 이 문제는 틀렸을 것이다.

다른 풀이1

n = int(input())
count = 0

while n > 0:
    if n % 5==0:
        count += n//5
        break
    
    n -= 2
    count+=1

if n < 0:
    print(-1)
else:
    print(count)

결과
코드는 거의 같지만 이런 형태로 작성할 수 있다는 의미에서 추가했다.

다른 풀이2

n= int(input())

result = -1

for i in range(n//5,-1,-1):
  if (n-i*5) % 2 == 0: 
      result = i + (n-i*5) // 2
      break

print(result)

결과
과정
- n을 5로 나눠준 값부터 0까지 i를 감소시킨다.
- n을 5로 나눠준 후 남은 값이 짝수이면 그 수만큼 합해서 동전의 개수로 출력해준다.
- 짝수가 아니라면 초기값대로 -1을 출력해준다.
다른 풀이는 2를 빼면서 값을 구했다면 이 풀이는 5의 개수를 줄이면서 값을 구했다.
시간이 더 오래 걸렸는데 이는 if문 내에 연산식이 들어가서 그런 게 아닌가라고 추측하였다.