[python] 백준 2839 : 설탕 배달

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

2839번: 설탕 배달

난이도 브론즈1

알고리즘 분류 : 수학, 다이나믹 프로그래밍, 그리디 알고리즘

---

그리디 알고리즘은 가장 큰 단위부터 거슬러주는 방법이다.

5kg 봉투를 몇개를 써야할지에 대해 초점을 두고 문제를 풀었다.

 

N에 설탕의 무게를 입력받는다.

N을 3kg, 5kg 봉투를 이용해 나눌때 봉지수를 최소화 한다면 몇개가 되는지를 출력한다.

 

1 : 먼저 3kg씩 덜면서 봉투에 담는 방법

N = int(input())
kg_3 = 0
kg_5 = 0
while N > 0:
    if N % 5 != 0:
        N -= 3
        kg_3 += 1
    if N % 5 == 0:
        kg_5 += (N // 5)
        N -= (5 * (N // 5))
if N == 0:
    print(kg_3 + kg_5)
else:
    print(-1)

실제로 설탕 Nkg에 봉투를 담는 모습을 생각하면서 코드를 구현했다.

 

N이 18kg라면 3kg씩 먼저 봉투에 담으면서 개수를 새는 방법이다.

첫번째 조건문에서 N이 5의 배수가 아니라면 3씩 빼고, 3kg 봉투의 개수를 kg_3에 1을 더해주는 방법으로 표현했다.

18 -> 15 (3kg 봉투 1개)

 

두번쨰 조건문에서 N은 5의 배수가 되기 때문에 15를 5로 나눈 값 3을 kg_5에 더해줌으로써 5kg 봉투 개수가 3개임을 표현했다.

그리고 N에다가 15를 빼주었다.

반복문이 다시 처음 위치로 돌아가면 N은 0이 되므로 자동으로 반복문을 탈출할 수 있게 된다.

N == 0인 경우는 설탕 Nkg을 두 가지 봉투로 남김없이 소분을 완료한 경우이므로 kg_3과 kg_5의 합을 출력하도록 한다.

 

 

N이 4kg이라면 첫번째 조건문에 따라 N=1, kg_3=1이 될 것이다.

그러나 두번째 조건문은 N이 5의 배수가 아니므로 실행되지 않고, 다시 첫번째 조건문으로 돌아간다.

여기서 또 N에다 3을 빼버리면 반복문의 조건인 N>0을 만족하지 못하게 됨으로, 다시 반복을 하게되면 자동으로 반복문을 벗어나 -1을 출력하게 될 것이다.

 

---

2 : while ~ else문을 이용한 풀이

while문은 조건문이 거짓이 될 때까지 실행문을 반복 수행한다.

N = int(input())
kg_3 = 0
kg_5 = 0
while N >= 0:
    if N % 5 == 0:
        kg_5 += (N // 5)
        print(kg_3 + kg_5)
        break
    N -= 3
    kg_3 += 1
else:
    print(-1)

조건식이 거짓이 되면 실행문을 수행하지 않고 while 바깥에 있는 else절의 실행문을 수행한다.

그러나 위의 코드처럼 N이 5의 배수가 되었을때는 break문을 만나 else절을 수행하지 않고 프로그램을 종료시킨다.