백준 2839 설탕배달

 

 

주어진 N을 5와 3만을 사용하면서 가장 적은 수의 5와 3으로 나타내는 문제이다.

 

풀이과정

 $N = 5x + 3y$ 라 할때, $x$가 클수록 $x+y$가 작아질 것이다. 예를 들어, 30이라면 5를 6개 쓰는 것이, 3을 10개 쓰는것 보다 낫다.

1. 위에 썼듯, 5를 최대한 많이 사용하기 위해서 먼저, N이 5로 나누어 지는지 확인한 후,  나누어 진다면 answer에 N을 5로 나눈 몫을 더한 후 반환한다.

2. N이 5로 나누어지지 않는 경우에는, N에서 3을 빼준 후, answer 에 1을 더한다(3을 한번 사용).

3. N이 0이 될때까지 1~2 과정을 반복하되, N이 음수가 되는 경우에는 N이 5와 3만으로 표현되지 않는 것이므로 -1을 반환한다.

 

Python Code

n=int(input())
answer = 0
while n != 0:
    if n%5==0:
        answer+=n//5
        print(answer)
        break
    else :
        n-=3
        answer+=1
        if n==0:
            print(answer)
            break
    if n<0 :
        print(-1)
        break