파이썬 Python | 알고리즘 | 백준 거스름돈

⭕ 파이썬 Python | 알고리즘 | 백준 거스름돈 

➡️ 문제링크

• https://www.acmicpc.net/problem/14916

 

➡️ 문제 탐색하기

• 2원과 5원 동전만을 사용하여 특정 금액을 거슬러 주는 문제이다. 가장 직관적인 방법은 큰 단위의 동전을 우선적으로 사용하는 것이다. 14원을 거슬러 준다고 가정하면, 처음에 5원으로 최대한 많이 나누어 보면 5원 세 개를 사용하면 15원이 되지만, 14원을 넘으므로 5원 두 개를 사용하면 10원이 되고, 남은 4원을 2원 두 개로 거슬러 줄 수 있다. 6원을 거슬러 준다면, 5원 하나를 사용하면 1원이 남아 불가능하지만, 2원 세 개를 사용하면 가능하다.
• 조건
  • 2원과 5원 동전만 사용하여 거스름돈을 주어야 한다.
  • 가능한 적은 개수의 동전을 사용해야 한다.
• 그리디 알고리즘 선택 
  • 5원을 최대한 많이 사용하는 것이 직관적으로 최적의 선택처럼 보인다. 5원 동전은 2원 동전보다 가치가 크기 때문에, 최대한 많이 사용하는 것이 총 동전 개수를 줄이는 데 유리한다.
  • 하지만 5원으로 나누어떨어지지 않는 경우가 있으므로, 반복문을 통해 5원의 개수를 하나씩 줄이며 남은 금액이 2로 나누어떨어지는지 확인해야 한다.

 

➡️ 코드 설계하기

• sys.stdin.readline을 사용하여 입력한다. 
• N을 5로 나눈 몫을 five에 저장한다.
• 반복문을 통해 five의 값을 하나씩 줄여가며, 남은 금액이 2원으로 나누어 떨어지는지 확인한다.
• 나누어 떨어진다면, 해당 개수의 5원 동전과 남은 금액을 2원으로 나눈 개수를 합쳐서 출력한다.
• 반복문을 다 돌았음에도 조건을 만족하지 않으면 -1을 출력한다.

 

➡️ 시도 회차 수정 사항 (Optional)

1회차

• 시간 88ms
• 최악의 경우, 반복문은 N // 5번 반복되므로 반복문의 시간 복잡도는 O(N/5)이다. 상수 계수를 무시하면 O(N)으로 표현할 수 있다.

import sys

N = int(sys.stdin.readline())

count = 0
five = N // 5

while five >= 0:
    if (N - five * 5) % 2 == 0:
        print((N - five * 5) // 2 + five)
        break
    five -= 1
else:
    print(-1)

 

➡️ 정답 코드

import sys

N = int(sys.stdin.readline())

count = 0
five = N // 5

while five >= 0:
    if (N - five * 5) % 2 == 0:
        print((N - five * 5) // 2 + five)
        break
    five -= 1
else:
    print(-1)