본문 바로가기
파이썬/파이썬 알고리즘

파이썬 백준 2839번 설탕 배달

by Go! Jake 2021. 2. 11.

 

문제

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

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

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

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

 

 

풀이 과정

- 5를 기준으로 코딩을 완성한다. 따라서 5로 나눠지는지 우선 본다.

- 5를 하나씩 빼면서 3으로 나눠본다. 이는 5를 최대한 많이 쓰기 위한 방법이다.

- 5를 써 가면서 맞아떨어지는 경우가 하나라도 없으면 3으로 나눠본다.

- 3으로도 없으면 -1 출력한다. (조합이 없을 땐 -1 출력)

풀이

N=int(input())

a=N%5
c=N//5

b=N%3
d=N//3

if a ==0:
    print(N//5)
elif a!=0:
    for i in range(c,-1,-1):
        if (N-i*5)%3==0:
            e=(N-i*5)//3
            print(e+i)
            break
        elif (N-i*5)%3!=0 and i==0:
            print(-1)
            break

N=int(input())

input()으로 입력되는 값을 문자열로 표출한다. 입력을 int()을 통해 정수형으로 만든다.

if a ==0:

    print(N//5)

a=N%5로, a는 N을 5로 나눴을 때 나머지다. 나머지가 0인 경우는 5의 배수이므로, 봉지 최솟값이 된다. 따라서 답이다.

elif a!=0:

    for i in range(c,-1,-1):

    if (N-i*5)%3==0:

        e=(N-i*5)//3

        print(e+i)

        break

5의 배수가 아니라면, N에서 5를 몇 개씩 뺐을 때 3으로 나누어 지는지 찾는다. 5와 3의 조합을 찾는 것이기 때문이다.

c=N//5이므로 N을 5로 나누었을 때의 몫이 된다. 몫이 최댓값이므로 최댓값부터 넣어주고 찾아본다. 왜냐면 5가 최댓값일 때가 봉지의 최솟값일 것이기 때문이다.

이 경우는 결과적으로 5를 하나도 빼지않고 3으로 나누는 결과도 포함한다.

elif (N-i*5)%3!=0 and i==0:

    print(-1)

    break

마지막으로 어느 값도 3으로도 안나누어지고 i==0인 마지막 값에 도달하면 -1를 표출하도록 한다.

 

댓글