[백준 2839번] 설탕 배달 - Python(파이썬) 자세한 풀이

1. 문제

 

 백준 2839 번

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

2839번: 설탕 배달

 

2. 아이디어

  

   사실 이문제에 대한 일반적 풀이법은 DP 혹은 그리디인데

 

   그리디를 기반하여 생각을 정리하던 중 시간복잡도가 상수인 아주 간단한 풀이가 떠올랐다.

 

   아이디어는 다음과 같다.

 

   문제를 다음과 같이 수식적으로 표현해 보자.

 

   N = 3*X + 5*Y 

 

   여기서 N은 주어진 설탕 무게의 합이며 X, Y는 각각 3kg 봉지의 수와 5kg 봉지의 수이다.

 

   문제 조건만 잘 이해했다면 위 수식이 그리 어렵지 않을 것이다.

 

   여기서 문제의 목표는 (X+Y) 의 최솟값을 구하면 되는것이다!

 

   그럼 'X를 1부터 N까지 차례대로 쳐 넣어보면 되겠네? '

 

   라고 생각하면 너무 비효율적이다

 

   일단 X를 N까지 넣을 필요도 없다. N을 넣게 되는 경우 이미 수식의 우변이 3*N으로 N보다 훨씬 크게 된다.

 

   즉, X는 1부터 N//3 까지 넣어보는게 합당하다.

 

   다만 X를 1부터 N//3 까지 대입하는 것 보다는 Y를 1부터 N//5 까지 대입하는게 더 효율적일 것이다

 

   여기까지는 뭐 특이한건 없지만 다음이 중요하다

 

   우리는 1부터 시작할 필요도 없다 그냥 N//5-2 부터 N//5 까지

 

   그러니까 Y에 N//5-2, N//5-1, N//5만 대입하면 끝난다

 

   '???????'

 

   자 당황하지말고 생각해보자

  

   N = 3*X + 5*Y 를 만족시키는 X, Y가 존재한다고 해보자

 

  그런데 이때, X+5 와 Y-3 도 다음과 같이 위 수식을 만족시킨다

 

  N = 3*(X+5) + 5*(Y-3) = 3*X + 15 + 5*Y - 15 = 3*X + 5*Y !

 

  하지만 알다시피 X+Y가 (X+5)+(Y-3) 보다 작기에 답은 X+Y이다 

 

  그러면 굳이 Y-3은 대입해볼 필요가 없다

 

  이제 이해가 되었는가? 

 

  한 줄 정리

 

  N = 3*X + 5*Y 를 만족하는 X+Y중 최솟값을 구하기 위해 우리는 Y에 N//5, N//5-1, N//5-2만 대입하면 된다

  

3. 코드

N = int(input())
cnt = -1

Y_lst = [N//5, N//5-1, N//5-2]

for Y in Y_lst :
    # Y < 0 이거나 N-5*Y < 0 인 경우는 식을 만족하는 X, Y를 구할 수 없다
    if Y < 0 or (N-5*Y) < 0 :
        continue
        
    # 이제 식을 만족시키는 X와 Y를 찾아보자
    if (N-5*Y)%3 == 0:
        X = (N-5*Y)//3
        cnt = X+Y
        
print(cnt)

 깔끔하다

 

 궁금한점이나 보완점은 댓글로!