C++에서 길이가 p, q, r인 세그먼트 개수 최대화하기

문제 설명

길이가 L인 막대가 하나 주어져 있으며, 이 막대를 잘라 길이가 각각 p, q, r인 세그먼트의 총 개수를 최대화하는 것이 목표입니다. 단, 세그먼트의 길이는 반드시 p, q, r 중 하나여야 하며, 그 외의 길이로는 자를 수 없습니다.

예를 들어 l = 15, p = 2, q = 3, r = 5라고 가정하면 다음과 같이 7개의 세그먼트를 만들 수 있습니다.

{2, 2, 2, 2, 2, 2, 3}

길이 2짜리 세그먼트 6개와 길이 3짜리 세그먼트 1개를 합치면 정확히 15가 되므로, 이 조합이 만들 수 있는 최대 개수입니다.

알고리즘: 동적 계획법(Dynamic Programming)

이 문제는 동적 계획법을 이용하면 효율적으로 해결할 수 있습니다. 각 위치까지 도달했을 때 만들 수 있는 최대 세그먼트 개수를 배열에 기록하며 앞으로 진행하는 방식입니다.

1. dp 배열을 -1로 초기화한 뒤, 시작점인 dp[0]을 0으로 설정합니다.
2. 0부터 막대의 길이 l까지 순회하며, 현재 위치 i에 도달할 수 없는 경우(dp[i] == -1)는 건너뜁니다.
3. 도달 가능한 위치에서는 p, q, r만큼 잘랐을 때 막대 범위를 벗어나지 않는다면 dp[i+p] = max(dp[i+p], dp[i] + 1), dp[i+q] = max(dp[i+q], dp[i] + 1), dp[i+r] = max(dp[i+r], dp[i] + 1)로 값을 갱신합니다.
4. 모든 순회가 끝난 후 dp[l]에 저장된 값이 만들 수 있는 최대 세그먼트 개수입니다. 해당 길이를 p, q, r의 조합으로 정확히 나누는 것이 불가능하면 -1이 반환됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int getMaximumSegments(int l, int p, int q, int r){
    int dp[l + 1];
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int i = 0; i <= l; ++i) {
        if (dp[i] == -1) {
            continue;
        }
        if (i + p <= l) {
            dp[i + p] = max(dp[i + p], dp[i] + 1);
        }
        if (i + q <= l) {
            dp[i + q] = max(dp[i + q], dp[i] + 1);
        }
        if (i + r <= l) {
            dp[i + r] = max(dp[i + r], dp[i] + 1);
        }
    }
    return dp[l];
}
int main(){
    int l = 15, p = 2, q = 3, r = 5;
    cout << "Number of segments = " << getMaximumSegments(l, p, q, r) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Number of segments = 7

복잡도 분석

막대의 각 위치를 한 번씩 순회하므로 시간 복잡도는 O(l)이며, dp 배열의 크기에 비례하므로 공간 복잡도 역시 O(l)입니다. 완전 탐색으로 모든 조합을 확인하는 것보다 훨씬 효율적으로 답을 구할 수 있습니다.