[백준] 2839번 설탕 배달 (파이썬)

 

문제

 

2839번: 설탕 배달

 

 

풀이 (Python)

 

N=int(input())

share=N//5
min_number=N
kg5_count,kg3_count=0,0
for i in range(share,-1,-1):
    if (N-5*i)%3==0:
        kg5_count=i
        kg3_count=(N-5*i)//3

    if min_number>kg5_count+kg3_count and(kg5_count>0 or kg3_count>0):
        min_number=kg5_count+kg3_count

if kg5_count==0 and kg3_count==0:print(-1)
else:print(min_number)

 

설명  (Python)

 

이 문제는 14916번 거스름돈 문제와 매우 유사한문제이다.

두 문제 모두그리디 알고리즘 대표문제격이기에 거스름돈 문제도 풀어보길 권장한다.

 

[백준] 14916번 거스름돈 (파이썬)

 

설탕 배달 문제의 경우 첫 풀이에서 생각보다 매우 난관이였는데, 최소 자루를 만들어야 하기 때문에 5로 먼저 나누고 나머지를 3으로 나눈 갯수로 풀이를 진행하려했다.

 

12인 경우 5kg하나에 3kg2개로 풀이하여야 하는데  위의 풀이 방식대로 진행하면 5kg 2개에 2kg가 남기에 불가하였다.

이와 같은 문제를 해결하기 위해 for문을 통해 5로 나누는 몫을 조절하여 풀이하였다.

 

for i in range(share,-1,-1):
    if (N-5*i)%3==0:
        kg5_count=i
        kg3_count=(N-5*i)//3

    if min_number>kg5_count+kg3_count and(kg5_count>0 or kg3_count>0):
        min_number=kg5_count+kg3_count

 

이후 5kg자루개수와 3kg자루 개수를 더한 값이 최솟값이여야 하므로 min_number변수를 만들어 if문을 통해 최솟값을 저장하였다.

 

for문 맨 끝에는 i가 0이 되기때문에 만들 수 없는 경우의 수를 예외처리하여 아래와 같이 작성하였다.

 

if kg5_count==0 and kg3_count==0:print(-1)
else:print(min_number)