백준 (Baekjoon Online Judge) 그리디 - 2839번 설탕 배달

설탕배달 문제를 보고 떠올린 아이디어

1. 5KG 봉지로 최대한 담는다.

2. 남은 설탕을 3KG 봉지에 담는다. 

였는데...

1kg -> x

2kg -> x

3kg -> 3kg 1개

4kg -> x

5kg -> 5kg 1개

6kg -> 3kg 2개

7kg -> x

8kg -> 5kg 1개, 3kg 1개

9kg -> 3kg 3개...

이런 식으로 진행되는데

일단 5kg에 최대한 담아야 하는 것은 확실하다. 최소한의 봉지 갯수만 사용해야 하니깐. 

그래서 남은 3kg에 어떻게 담을것인지 생각해봤는데, 5KG봉지에 최대한 담으면 이후에 세가지 경우의 수가 생긴다.

• 5kg에 다 담고 3으로 나눈 나머지가 0인 경우
• 5kg에 다 담고 3으로 나눈 나머지가 1인 경우
• 5kg에 다 담고 3으로 나눈 나머지가 2인 경우

이 세가지 경우에 따라 코딩을 진행했다.

a = int(input())
sum = 0
num5=0
num3=0
if a %5==0: #5에만 담아도 된다면
  num5 = a//5
else: #5와 3에 섞여 담거나.. 등등
  num5 = a//5 # 먼저 5에 최대한 담는다.
  k = a-5*num5 # 5에 담은만큼 입력받은 무게에서 빼준다.
  #print(num5,k)
  if k%3==1: #남은 무게를 3으로 나눈 나머지가 1이면?
    num5 = num5-1 #num5를 하나 빼주고
    k = k+5 #남은 무게 +5를 해준뒤
    num3 = k//3 #3으로 나눈 몫을 num3에 저장한다.
    #print("num5 =",str(num5),"num3 =", str(num3))
  elif k%3==2: #남은 무게를 3으로 나눈 나머지가 2이면?
    num5=num5-2 #num5에서 봉지 두개를 뜯어서 
    k = k+10 #남은 무게 +10를 해준뒤
    num3 = k//3 #3으로 나눈 몫을 저장
    #print("num5 =",str(num5),"num3 =", str(num3))
  else: #3으로 나누어 떨어지면 좋고
    num3 = k//3
    #print("num5 =",str(num5),"num3 =", str(num3))
  
if num5<0 or num3<0: #근데 5kg봉지나 3kg봉지의 갯수가 음수라면?
  print(-1) #나누어 떨어지지 않는 수이므로 -1출력
else:
  sum = num5+num3 #아니면 출력
  print(sum)

일단 3으로 나눈 나머지가 1인 경우 5kg봉지를 하나 뜯어 6kg을 만들면 3kg 두 봉지로 바꿀 수 있다.

또 비슷한 방법으로 3으로 나눈 나머지가 2인 경우 5kg봉지를 두개 뜯어 12(10+2)kg을 만들면 3kg 네 봉지로 바꿀 수 있다.

 

결과는 성공~!

아이디어 떠올리기는 어렵다...!

 

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