[백준] 2839번: 설탕 배달

 

이번 문제는 백준 난이도 실버4인 '설탕 배달' 문제다.

 

 

 

이 문제는 최대 5000kg의 설탕을 5kg, 3kg의 두 봉지를 이용해 최대한 작은 봉지의 수를 사용해서 5000kg의 설탕을 딱

맞아떨어지게 운반하는 봉지수를 구하는 문제다.

 

일단 이런 문제는 특별한 수학적 공식이 존재하지 않는다.

그리고 입력값 또한 5000이하로 작기 때문에 직접 모든 경우의 수를 시도해서 구하는 브루트포스 방법으로 해결하는 게

코드도 단순하고 효율적이다.

 

.

 

 

그렇다면 모든 경우의 수를 시도하려면 어떻게 하면 될까?

일단 문제의 특징을 보면 봉지의 수를 가장 작게 사용하는 것이 목표다.

그렇다면 5키로의 봉지를 최대한 많이 사용하고 남은 설탕을 3키로로 딱 맞아떨어지게 사용하면 된다.

가장 빠르게 구하기 위해선 5키로의 봉지를 최대한 사용했을 때부터 사용횟수를 1씩 줄여나가면서

나머지를 3키로로 사용했을 때 남은 설탕이 없이 딱 맞아떨어지는 경우를 찾으면 된다.

 

쉽게 말해 설탕이 42kg라고 치면

5kg 봉지 8개 사용 후 나머지 3kg 봉지 사용 → 40 + 3 = 43         X

5kg 봉지 7개 사용 후 나머지 3kg 봉지 사용 → 35 + 9 = 44         X

5kg 봉지 6개 사용 후 나머지 3kg 봉지 사용 → 30 + 12 = 42       O 

이렇게 5kg 봉지 수 사용갯수를 줄여나가면서  딱 맞아떨어지게 사용한 경우를 찾아나가면 된다.

 

최대 입력 값 5000일때

최적의 경우 1번만에 목표값을 찾을 수 있고

최악의 경우 1000번 반복한다.

 

O(N/5)의 시간으로 표현할 수 있는데 이건 → O(N)의 시간으로 볼 수 있다.

즉 이런 문제처럼 특별한 공식이 없고 입력값도 작다면 브루트포스 방식으로 푸는 것도 좋은 방법이다.

 

1초에 약 1억번 연산

입력 5000 → O(N) : 1초에 5000번 연산

 

---

 

[Python]

 

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

for i in range(N // 5, -1, -1):
    new = N - (i * 5)
    if new % 3 == 0:
        result = i + (new // 3)
        break
print(result)

 

 

문제의 조건 중에 모든 경우의 수를 돌았음에도 5kg, 3kg 봉지로 설탕을 딱 맞게 사용하지 못하는 경우엔 -1을 출력하도록 돼있다.

그래서 기본 결과값은 -1로 설정하고 중간에 만족하는 경우를 찾으면 값을 갱신하도록 한다.

 

우선 가장 적은 갯수의 봉지를 사용한 경우를 찾기 위함이니 5kg 봉지를 가장 많이 사용한 경우부터 시작해서 1개씩 줄여나간다.

그러기 위해 for문을 역으로 돌아 순회한다.

입력값 N을 5로 정수 나눗셈한 값에서 시작해 1씩 줄어들며 역으로 루프를 돈다.

new 변수를 생성해 현재 설탕에서 5kg 봉지를 사용한 만큼 뺀다.

 

그 후 남은 설탕을 3으로 나눴을 때 맞아떨어지면,

result는 5kg 봉지를 사용한 갯수 i와 new값을 3으로 정수 나눗셈 했을 때 → 즉 3kg 봉지 사용 갯수를 더한 값을 대입한다.

 

이렇게 하면 최소로 사용한 봉지 갯수를 구할 수 있고 조건에 부합하지 않을 땐 result가 -1로 남게된다.