[파이썬] 단계별 백준 문제 풀기 - 2839 기본수학 (설탕 배달)

문제링크

2839번: 설탕 배달

 

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

 

---

<<코드소스>>

import sys
N = int(sys.stdin.readline()) #N은 설탕의 kg수이다
a = [] #a 리스트는 3kg 봉지 갯수의 경우의 수를 담을 것이다.

for i in range((N//3)+1): # N을 3으로 나눈 몫은 3kg짜리의 최대 갯수가 된다. 최대 갯수까지 나열한다 
  if (N - (3*i))%5 == 0: #N에서 3의 배수를 뺀 수가 5로 나누어져야한다. 즉 나머지가 0인 값들을 찾는다. 
    a.append(i) #위에 조건을 만족하면 i에 추가한다. 아니면 b에 버린다.

if len(a)==0: #for문을 끝내고 a리스트를 봤을때, a의 길이가 0이라면, 5로 나누었을때 떨어지는게 없다는 것
    print("-1") #출력이 불가능하므로-1을 출력한다
else: #만약 a의 리스트에 가능한것들이 담겼다면
    min_a = min(a) # a리스트에서 최소값을 뽑는다. 그래야 5kg 봉지가 최대가 된다.(=문제의 관건)
    new_a = 3 * min(a) #최소값에서 3을 곱해주고, 그 값을 N에서 빼준뒤 5로 나누면 5KG 봉지 갯수가 나온다
    result = (N - new_a) // 5 + min_a # 5KG 봉지 갯수에 + 3KG 봉지 갯수(min_a) 를 더해준다.
    print(result)

 

<<결과값>>

18

4

---

#코드설명

# N - 3x = 5y 의 경우로 볼때, y가 최대값이 되려면 N은 고정값이니 x가 최소값이여한다.

# x의 최대값을 구한다. y가 0일때, N을 3으로 나눈 몫이 x의 최대이다. +1로 range를 잡아준다

# N - 3x를 뺀 값이 5의 배수여야 하기 때문에, 5로 나눈 나머지가 0 이라면 모든 x값을 a 리스트에 넣어준다

# 아니라면 그냥 b에 넣는다 ( 버려도 되는데 어디에 버려야할지 몰라서 b를 만들어 넣어줌)

# 만약 a가 0이 아니라면, a리스트에서 min값을 찾아 3을 곱해준다. 그리고 N에서 그 값을 빼주고 5로 나누면 y의 최대값이 나온다.

# 이제 y의 최대값과 x의 최소값을 더하면 봉지의 최소값이 나온다. 

오류 발생 ㅠㅠ 

#런타임 에러 발생 -> -1 값을 생각 안해줬다. a 리스트가 빌 경우 -1을 출력해줘야한다.

#두번째 런타임 에러 발생, 시간초과 날것 같아서 input을 sys 로 바꿔줘놓고 sys 모듈을 import 안했다. 바보. input 고쳐주고 맞았다...