[Greedy] 백준 2839번 “설탕 배달” Python 풀이

문제 링크

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

풀이

• 남아있는 N이 5로 딱 나눠떨어질때까지 3씩 덜어냅니다.
• 세부 알고리즘은 아래 코드와 같습니다.
  • 입력이 9일땐,
  • N이 마지막에 0이 되더라도,
  • if (n % 5 == 0) 의 조건은 만족하므로, 3으로만 나눈 결과값이 출력됩니다.

코드

import sys

# 설탕 무게
n = int(sys.stdin.readline())
# 봉지 개수
bag = 0

while n >= 0 :
    if n % 5 == 0 :         # 남은 설탕이 5로 나눠떨어진다면
        bag += (n // 5)     # 5로 나눈 몫을 봉지 개수에 추가
        print(bag)
        break

    n -= 3      # 남은 설탕이 5로 나눠떨어지지않는다면, 3씩 덜어내기
    bag += 1    # 봉지 개수 추가

else:
    print(-1)