백준-2839-설탕 배달

구현

• 5kg 봉지로 최대한 담는 것이 최소의 봉지를 만드는 것이다.
• 5kg 봉지로 한번에 담을 수 없으면 3kg 봉지로 한 번 담고 다시 5의 배수인지 확인한다.
  • 만약 5의 배수가 나오면 모두 5kg 봉지로 담아내고 프로그램 종료

---

풀이 코드 1

N = int(input())

count = 0

while N > 0:
    #5의 배수인 경우
    if N % 5 == 0:
        count += 1
        N = N - 5
    #3의 배수인 경우
    else:
        count += 1
        N = N - 3

if N == 0:
    print(count)
else:
    print(-1)

• 처음 풀이한 코드로는 5의 배수 혹은 3의 배수가 나올때마다 3혹은 5를 빼주는 방식으로 구현했다.
• 하지만 5의 배수가 나오면 바로 최적의 답이 나오기에 이를 적용시켜서 아래코드를 작성했다.

풀이 코드 2

N = int(input())

count = 0
while N > 0:
    # 처음부터 5의 배수이면 5kg 봉지로 담는게 가장 최소의 조건
    if N%5==0:
        count += (N // 5)
        break
    
    # 처음이 5의 배수가 아니면 3kg를 담는다.
    N -= 3
    count += 1

    # 3kg 5kg로 담을 수 없는 상황은 count를 -1로 만든다.
    if N < 0:
        count = -1
    # 다시 한 번 5의 배수이면 한번에 담을 수 있게된다.
    elif N % 5 == 0:
        count += (N//5)
        break

print(count)

• 이 방식으로 제출하였을 때 시간이 조금 단축된 것을 확인했다.

 

문제 링크