코딩테스트 20일차(2025.02.09) - 백준2839번(설탕 배달)

문제유형

그리디 알고리즘

풀이 방법 도출 과정

1. 3킬로, 5킬로만 담을 수 있는 봉지가 있다. 주어진 킬로로 최소의 봉지수 구하기

2.5로 계속해서 나누면서 카운트하는 방식으로 이를 풀어보도록 하겠다.

 

시간 복잡도

시간복잡도는 입력 후 for문이 최대 1번 사용되고 있기 떄문에 O(n)이다. 

코드 및 간단설명

그리다 알고리즘과 완전 탐색 알고리즘을 사용하여 

def min_bags(n):
    # 5kg 봉지를 최대한 많이 사용
    for i in range(n // 5, -1, -1):  # 5kg 봉지 개수를 줄여가면서 탐색
        remainder = n - (i * 5)  # 5kg 봉지를 사용하고 남은 무게
        if remainder % 3 == 0:  # 나머지가 3으로 나누어 떨어지는 경우
            return i + (remainder // 3)  # 5kg 봉지 개수 + 3kg 봉지 개수
    return -1  # 정확한 무게를 만들 수 없는 경우

# 테스트 실행
n = int(input())
print(min_bags(n))