설탕 배달(2839)

문제 📄

입력으로 N kg의 설탕이 주어질 때, 상근이는 3, 5kg 봉지만으로만 N kg을 만들어서 배달한다. 이때 총 봉지의 최소 개수를 출력해야한다. 3,5kg으로 주어진 N을 만들 수 없다면 -1을 출력해야한다. (N은 3이상 5000이하의 정수이다.)

1. 상식적인 풀이 💡

상식적으로 무거운 5kg짜리를 더 많이 들고가면 상대적으로 3kg짜리는 덜 들고간다. 즉 5kg짜리가 많을수록 전체 봉지수는 적어진다.

주어진 입력 N에서 3을 계속해서 뺀다.
- 3을 뺀 횟수는 바로 3kg 짜리 봉지의 개수이다.
계속 빼다가 N이 5의 배수가 된다면 멈춘다. 이 값을 5로 나눈 몫이 5 kg짜리의 개수이다.
만약 음수가 되었다면 -1을 출력한다. 주어진 입력 N에서 3을 빼서 0이상의 5의 배수를 만들 수 없다. 즉 3, 5의 배수의 합으로 N을 만들 수 없음을 말한다.

코드 💾

def main()->None:
    N = int(input())

    three_count = 0
    # 음수가 아닌 동안 3씩 빼며 5의 배수로 만들기
    while N >= 0:
        if N % 5 == 0:
            print(three_count + N // 5)
            return
        else:
            N -= 3
            three_count += 1
    # N을 5의 배수로 만들 수 없음.
    print(-1)

if __name__ == "__main__":
    main()

2. 수학적 풀이 📊

3kg 봉지를 개, 5kg 봉지를 개 들고 간다고 할때, 이고 구해야하는 것은 의 최솟값이다. 이때 는 0이상의 정수이다.

에서 에 관해 정리하고, 의 에 대입하면 는 증가하는 일차함수이다.

그리고 를 와 나머지 의 합으로 되어있다고 하자.

그러면 을 3의 배수와 나머지 의 꼴로 만들 수 있다.

chart1

라 두면 이다. 는 0이상의 정수 이므로 위의 표처럼 값들을 나열해 볼 수 있다. 세번째 행에는 의 값들을 나열했다.

이때 도 0이상의 정수가 되어야하므로 의 값이 5의 배수가 되어야 정수 값을 구할 수 있다.

에 의해 는 항상 증가하고, 제일 처음 만나는 5의 배수 의 값에서 5를 나눠 를 구해 가장 최소인 의 값을 찾으면 된다.

그러고 만약에 5의 배수인 을 끝까지 찾지 못했다면 정수 값을 찾을 수 없으므로 -1을 출력하면 된다.

코드 💾

def main() -> None:
    N = int(input())

    """
        N = 3x + 5y이고, 5y = 3Q+R (R = 0,1,2)라 하자.
        N = 3x + 3Q + R
          = 3(x + Q) + R
          = 3 * quot + R
    """
    quot, R =  N // 3, N % 3

    # x = 0부터 차례로 탐색
    # 5의 배수인 3Q+R를 처음 구하면 답을 출력하고 종료
    for x in range(0, quot + 1):
        # x + Q = quot
        Q = quot - x
        five_y =  3 * Q + R

        # 3Q + R이 5의 배수면 y 탐색 성공
        if five_y % 5 == 0:
            print(x + five_y // 5)
            return

    # 5의 배수인 3Q+R을 찾지 못함.
    print(-1)

if __name__ == "__main__":
    main()

반복문의 반복횟수는 번 이기에 시간 복잡도는 (아마도) 이다.

3. Dynamic Programming 풀이

주어진 입력 N kg을 생각해보면, N-3 kg을 3,5kg으로 어떻게든 만들고, 거기에 3kg 한봉지를 더하면 된다. 비슷하에 N-5 kg도 마찬가지이다.

그렇다면 우리가 알고싶은 N kg을 만드는 최소 봉지 개수는 위와 같이 둘 중에 작은 값에 한 봉지를 더하면 된다. 즉 주어진 N kg에 대한 문제를 두 개의 소문제(Subproblem)로 쪼개어 분석했다. 이런식으로 계속 쪼개다보면 쉽게 구할 수 있는 작은 숫자까지 내려가고, 거기서부터 계산을 해서 거꾸로 올라가면 N kg에 대한 답을 구할 수 있다.

(N은 3~5000사이의 값) 4kg은 3,5kg 봉지로 만들 수 없으므로 답은 -1이고, 3,5kg은 각각 3,5kg 한 봉지로 만들 수 있으므로 답은 1이다. 그리고 6부터 N까지 반복문을 통해 위의 min(...) + 1의 식을 써서 Bottom-up 방식으로 문제의 답을 구할 수 있다.

코드 💾

def main() -> None:
    N = int(input())

    # 3 ~ 5000kg 까지 답을 저장할 배열
    dp = [-1] * 5001
    # 3, 5kg은 1 봉지로 만들 수 있다.
    dp[3] = dp[5] = 1

    # 6~N kg까지 정답 구하기
    for i in range(6, N + 1):
        # 둘다 -1이 아닌 경우에만 min(...) + 1
        if dp[i - 3] != -1 and dp[i - 5] != -1:
            dp[i] = min(dp[i - 3], dp[i - 5]) + 1

        # 둘 중에 하나가 -1인 경우: -1이 아닌 값에 1을 더한다.
        elif dp[i - 3] == -1 and dp[i - 5] != -1:
            dp[i] = dp[i - 5] + 1
        elif dp[i - 3] != -1 and dp[i - 5] == -1:
            dp[i] = dp[i - 3] + 1

        # 둘다 -1인 경우: 3,5kg로 만들 수 없는 값
        else:
            dp[i] = -1

    # N kg에 대한 정답 출력
    print(dp[N])

if __name__ == "__main__":
    main()