#3_ 설탕 배달(백준 2839번, 파이썬 풀이)

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그래 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3<=N<=5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

예제입력: 18

예제출력: 4

---

먼저 정답으로 인정된 코드는 아래와 같습니다.

n = int(input())
F = n//5
n%=5
T = 0
while F>=0:
    if n%3 == 0:
        T = n//3
        n = n%3
        break
    F-=1
    n+=5
print((n==0) and (F+T) or -1)

문제를 정리해보면, N = a*5 + b*3 이 되도록 하는 (a+b)의 최소값을 구하라는 것입니다.

어찌되었든, N이라는 숫자가 위의 식과 같이 분해되게 하는 a,b를 찾는게 우선이라고 생각됩니다.

그 다음으로, a,b 합의 최소값을 찾는 순서가 되겠죠?

먼저, a,b 합의 최솟값을 갖는 경우는 어떠한 경우일까요?

입력으로 받은 숫자 N을 두개의 식으로 풀어낼 때, 5와 곱셈이 되는 숫자가 크게, 즉 숫자 a가 크게하는 것이 좋을 것입니다.

간단한 예를 들어서, 15라는 숫자가 있을 때, a를 크게하면 a=3, b=0 이 되어 a+b = 3이 될 것이고, b를 크게하면 a=0, b=5가 되어 a+b = 5가 될 것이기 때문입니다.

그럼 이제 풀이 알고리즘을 생각해보겠습니다.

일단, 숫자 N이 주어졌을 때, 이를 n으로 받겠습니다. 그리고, n을 먼저 5로 나누어 봅니다.

n = a*5 + k

나머지 k가 발생하겠죠?

만약 나머지 k가 0이라면 바로 끝내면 되겠지만 아닌 경우가 있을 것입니다.

그렇다면 나머지 k를 3으로 나누어 봅니다.

k = b*3 + i

이와 같이 여기서도 나머지 i가 발생합니다. 역시나, 나머지 i가 0이라면 이제 끝내면 됩니다.

그런데 i도 0이 아니라면 어떻게 할까요? 어쩔 수 없이, a를 하나 줄여 k를 5만큼 증가시켜야 합니다.

조금더 자세히 살펴볼게요.

i가 가질 수 있는 값은 0,1,2 총 3가지 입니다. 3으로 나눈 나머지이기 때문이죠.

만약 i가 0일땐, 그대로 출력을 하면 됩니다.

i가 1일땐, k값에 5를 추가하면 되겠죠?

k = b*3 + 1 이므로,

k+5 = b*3 +1 +5 = (b+2)*3 + 0 이기 때문입니다.

마찬가지로, i가 2일때는 k 값에 10을 추가하면 될 것입니다.

근데 k값에 5나 10을 추가하는 방법은 무엇이 있을까요?

네, 앞에서 계산한 a를 하나 또는 둘을 줄이면 됩니다.

이러한 알고리즘을 코드로써 구현하면 아래와 같이 구현됩니다.

n = int(input())
F = n//5
n%=5
T = 0
while F>=0:
    if n%3 == 0:
        T = n//3
        n = n%3
        break
    F-=1
    n+=5
print((n==0) and (F+T) or -1)

먼저 1번라인에서 입력값을 받습니다.

그리고 먼저 F에 입력값을 5로 나눈 몫을 저장하고, n을 그 나머지로 바꿔줍니다.

그리고 F가 0보다 클동안 반복문을 실행하는데, F가 음수가 되버리면 말이 안되기 때문에 반복문을 종료하는 것입니다.

그리고 반복문 내에서는, 위에서 얻은 나머지 n을 3으로 나눴을 때 0이 될 때 T에 그 몫을 저장하고 반복문을 끝냅니다.

n을 3으로 나눴을 때 나머지가 0이 아니라면, F를 하나 줄이고 n에 5를 더하게 되죠.

이렇게 해서 맨 마지막 12번 라인에서 최종 나머지 n이 0일 때는 F+T를 출력하고, n=0이 아닐때는 5와 3을 통해 입력값을 만들 수 없는 것이므로 -1을 출력합니다.