[ python ] 백준 2839: 설탕 배달

 

안녕하세요? 수구리입니다.

이번 포스팅은 파이썬으로 그리디 문제를 풀어보려고 합니다.

그리디 알고리즘은 매 순간마다 이름처럼 가장 탐욕스러운 선택을 하는 알고리즘입니다.

하지만 이 알고리즘은 최적의 해를 찾는다는 보장은 하지 못합니다.

설탕 배달 문제는 아래 링크에 있으니 확인해주세요.

 

 

[ 문제 ] 백준 2839: 설탕 배달

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

2839번: 설탕 배달

 

 

[ 나의 풀이 ]

# date : 2021.11.12
# problom : 2839
# title : 설탕 배달
# description : 최소한의 설탕 봉지로 N kg의 무게의 설탕을 배달하자

import sys
input = sys.stdin.readline

N = int(input())
cnt = 0 # 설탕 봉지 수
while N >= 0:
    if N % 5 == 0:
        cnt += (N // 5)
        print(cnt)
        break
    N -= 3
    cnt += 1
else:
    print(-1)

[ 설명 ]

1. 총 배달해야 하는 설탕의 무게 값을 변수 N에다가 저장해준다.

2. 배달해야 하는 설탕 봉지의 수 변수를 cnt라고 선언해주고 동시에 0으로 초기화한다.

3. 총 무게가 0 보다 크다면 즉, 배달해야 하는 설탕의 무게가 남아있지 않을 때까지 반복한다.

4. 만약, 배달해야하는 설탕의 무게가 있고, 그 무게 값이 5kg으로 나눠 떨어진다면 (N의 값이 5의 배수 라면)

5. 배달해야 하는 횟수는 5로 나눈 몫이 되어지고, 그때 cnt값을 출력하면 끝.

6. N의 값이 5의 배수가 아니라면, 3kg으로 빼주고 cnt값을 1 증가시켜준다.

7. 3번 ~ 6번의 과정을 반복, 문제에서 주어진 조건에서 만약 N의 값이 나눠 떨어지지 않는다면 -1을 출력한다.