백준 알고리즘 2839 (설탕 배달) - python

[ 문제 ] 백준 알고리즘 2839 (설탕 배달) - python

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

2839번: 설탕 배달

 

설탕을 배달할 때, 정확히 N kg를 배달해야 하는데,

3, 5 kg의 조합으로 된 최대한 적은 봉지를 들고 가려고 한다.

 

그렇다면, 5 kg부터 최대한 많이 채울 수 있는 것이 효율적이라고 생각했다.

N kg를 채우기 위해선, 5 kg 봉지의 최대 개수는 N // 5 개이고, 3 kg 봉지의 최대 개수는 N // 3개이다.

 

5 kg 봉지는 최대 개수에서 최소 개수로 감소시키면서,

3 kg 봉지는 최소 개수에서 최대 개수로 늘리며 합이 N이 될 때 return 해주는 함수를 작성했다.

모든 조합이 만족하지 않으면, -1을 return한다.

 

[ Code ]

N = int(input())
N_3 = N // 3
N_5 = N // 5
def find_x_y(N):
    for y in range(N_5, -1, -1):
        for x in range(N_3+1):
            if y * 5 + x * 3 == N:
                return x+y
    return -1
print(find_x_y(N))

 

# range(K, -1, -1)은 K, K-1, ... 2, 1, 0 까지의 범위를 갖는다.