사용자 도구

사이트 도구


ps:problems:boj:2839

설탕 배달

ps
링크acmicpc.net/…
출처BOJ
문제 번호2839
문제명설탕 배달
레벨브론즈 1
분류

애드혹

시간복잡도O(1)
사용한 언어Python
제출기록29200KB / 68ms
최고기록52ms
해결날짜2021/10/01

풀이

  • 3킬로그램짜리 봉지를 0개~4개까지 사용해서 각각 N킬로그램을 만들었을때 총 봉지수중 최소갯수를 구하면 된다. 3kg 봉지를 그 이상으로, 5+a개를 사용하는 것은 5kg봉지 3개와 3kg봉지 a개를 사용하는 것보다 비효율적이므로, 고려할 필요가 없다.
  • 실제 구현은 5킬로그램 봉지의 수를 N/5개에서 N/5-2개까지 줄여가면서 계산했는데, 결국 비슷한 논리이다.
  • 5가지 또는 3가지의 경우 중에서만 최소값을 구하면 되므로 시간복잡도는 O(1).
  • 쿨한 물건 구매도 문제는 살짝 다르지만 유사한 방식으로 푸는 문제이다.

코드

"""Solution code for "BOJ 2839. 설탕 배달".

- Problem link: https://www.acmicpc.net/problem/2839
- Solution link: http://www.teferi.net/ps/problems/boj/2839
"""


def main():
    N = int(input())
    count_5, r = divmod(N, 5)
    while r % 3 != 0:
        r += 5
        count_5 -= 1
    print(count_5 + r // 3 if count_5 >= 0 else '-1')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Q᠎ P N Z Q
 
ps/problems/boj/2839.txt · 마지막으로 수정됨: 2021/10/01 17:30 저자 teferi