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()
ps/problems/boj/2839.txt · 마지막으로 수정됨: 2021/10/01 17:30 저자 teferi
토론