2839. 설탕 배달

문제가 궁금하시다면 아래의 링크를 눌러주세요!
문제 본문

접근 과정

• 3kg와 5kg의 설탕 봉지로 정확히 Nkg의 설탕을 배달해야 하는데, 설탕 봉지의 최솟값은 얼마일까?
  • 아쉽게도 3과 5는 배수의 관계가 아니기에, 단순하게 그리디한 풀이를 적용하기는 쉽지 않아보인다.
• 3과 5중에서는 5가 제일 크기 때문에, 가능하다면 N을 5로 나누어주는 것이 더 적은 설탕봉지를 사용하게 된다.
  • 5로 나누어떨어진다면 그 몫을 출력하고, 나머지가 있는 경우 이것이 3으로 나누어떨어지는지 확인한다.
  • 3으로 나누어떨어진다면 그 몫을 5로 나눈 몫에 더해주면 된다.
  • 만약 3의 배수가 아니라면 그 수에 5를 더한 뒤(5kg 설탕봉지 하나 차감) 다시 3으로 나누어떨어지는지 확인한다.
  • 이렇게 5kg 설탕봉지가 0이 될 때까지도 3으로 나누어떨어지지 않는다면 그 수는 3과 5로 나타낼 수 없는 수이다.
• 최대 데이터값이 5000으로 매우 작기에 설령 O(N^2)정도의 복잡도를 가지더라도 통과에는 문제가 없을 것이다!

풀이

N = int(input())
cnt = 0
five = N // 5
other = N % 5

for i in range(five, -1, -1):   # 5kg를 하나도 안 쓰는 경우도 있을 수 있기에(ex> 12) 0이 아니라 -1!
    if N == 3 or N == 5:    # N이 3인 경우를 계산하지 못했다. 문제를 잘 읽자...
        cnt = 1
        break
        
    if not other % 3:
        three = other // 3
        cnt = i + three
        break
    else:
        other += 5
else:
    cnt = -1


print(cnt)

읽어주셔서 감사합니다!