백준 2839 번 문제 풀이 Python 파이썬 :설탕 배달

#62. 백준 2839번 문제 풀이: 설탕 배달

설탕공장에서 설탕을 배달하고 있다. 사탕가게에 N킬로그램을 배달해야 한다. 봉지는 3킬로그램과 5킬로그램 봉지가 있다. N킬로그램을 배달할 때, 가장 적은 수의 봉지 수를 구하는 프로그램을 작성하시오. 입력: 첫줄에 배달할 총용량 N. (3 ≤ N ≤ 5000) 출력: 배달하는 데 필요한 최소의 봉지 개수 정확하게 N킬로그램이 되는 조합이 없으면 -1 출력.

입력/출력

--입력--
18
--출력--
4
--입력--
4
--출력--
-1
--입력--
6
--출력--
2

문제풀이+해설

가장 적은수의 봉지로 조합하려면, 큰 무게의 봉지를 최대한 많이 가져야가야 한다.
 N = 5 * n5 + 3 * n3; 

쉽게 계산하는 방법은 N 에서 3kg봉지(3)를 하나씩 늘려가면서 뺀값이 5로 나누어지면 그때 개수가 최대의 5kg 봉지와 최소의 3kg 봉지수가 된다.

1. N을 큰봉지(5)로 나누어 나머지가 0 이 되거나 N값이 0보다 작을 때까지 아래 과정을 반복한다. 
2. N = N - 3(3kg봉지)를 빼주고, 3kg봉지수(n3)를 +1 한다. 1번을 다시 확인한다.
3. 루프가 끝나고, N이 0보다 작으면 봉지조합이 없으므로 -1 출력.
4. N 값이 0이상이면 5로 나눈값(n5)이 5kg봉지수. 5kg봉지수(n5) + 3kg봉지수(n3) 값을 출력한다.

code sol.

코드편집/실행

N = int(input())
# 배달할 설탕량 N 값을 정수형으로 받는다.
if N % 5 == 0: # 5kg 봉지로 나누어 떨어지면 5로 나눈값이 최소봉지 값
  print(N // 5) # 최소봉지값 출력
else:  
  n3 = 0 # 3kg봉지수, 초기값 0개
  while N >= 0: # N 중량이 0이상이면 루프.
    n3 += 1 # 3kg 봉지를 하나씩 늘려가면서 계산
    N -= 3 # 3kg를 빼준다
    if N % 5 == 0: # 남은 중량이 5kg로 나눈 나머지가 0이면 조합 완성
      break;

  if N < 0: # 3kg, 5kg 봉지 조합이 없음
    print(-1)
  else :
    print((N // 5) + n3) # 5kg봉지수 + 나머지를 3kg봉지로 나눈수 = 조합봉지갯수 출력