문제 개요
0과 1로만 이루어진 문자열이 주어집니다. 이 문자열을 여러 개의 세그먼트(연속된 부분 구간)로 나누되, 각 세그먼트에 포함된 1의 개수가 0의 개수보다 많아야 한다는 조건을 만족해야 합니다. 목표는 이 조건을 충족하는 세그먼트들을 골라 그 길이의 합을 최대화하는 것입니다.
예시
입력 문자열이 "10111000001011"일 때 정답은 12입니다.
- 첫 번째 세그먼트: 길이 7 → "1011100" (1이 4개, 0이 3개)
- 두 번째 세그먼트: 길이 5 → "01011" (1이 3개, 0이 2개)
- 전체 길이 = 7 + 5 = 12
주목할 점은 모든 문자를 반드시 사용할 필요가 없다는 것입니다. 조건을 만족하지 않는 구간(이 예시에서는 가운데의 연속된 0들)은 건너뛰고, 유리한 구간만 선택함으로써 전체 길이를 극대화할 수 있습니다.
접근 방법 및 알고리즘
이 문제는 메모이제이션(memoization)을 활용한 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. dp[start]에는 start 위치에서 출발했을 때 얻을 수 있는 세그먼트 길이 합의 최댓값을 저장하여 중복 계산을 방지합니다.
- start == n이면 남은 문자가 없으므로 0을 반환합니다.
- dp[start] 값이 이미 계산되어 있다면(-1이 아니라면) 그 값을 그대로 반환합니다.
- start부터 n-1까지 반복하면서 각 끝점 k까지의 구간을 검사합니다.
- 현재 문자가 '1'이면 one 카운트를, '0'이면 zero 카운트를 증가시킵니다.
- one > zero이면 해당 구간을 세그먼트로 채택할 수 있으므로, 다음 위치(k+1)의 재귀 호출 결과에 구간 길이(k - start + 1)를 더해 dp[start]를 갱신합니다.
- 조건을 만족하지 않으면 구간을 채택하지 않고 다음 위치(k+1)의 재귀 호출 결과만 비교합니다.
- 모든 경우를 확인한 뒤 dp[start]를 반환합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
int getSegmentWithMaxLength(int start, string str, int n, int dp[]) {
if (start == n) {
return 0;
}
if (dp[start] != -1) {
return dp[start];
}
dp[start] = 0;
int one = 0;
int zero = 0;
int k;
for (k = start; k < n; ++k) {
if (str[k] == '1') {
++one;
} else {
++zero;
}
if (one > zero) {
dp[start] = max(dp[start], getSegmentWithMaxLength(k + 1, str, n, dp) + k - start + 1);
} else {
dp[start] = max(dp[start], getSegmentWithMaxLength(k + 1, str, n, dp));
}
}
return dp[start];
}
int main() {
string str = "10111000001011";
int n = str.size();
int dp[n + 1];
memset(dp, -1, sizeof(dp));
cout << "Maximum length of segment = " << getSegmentWithMaxLength(0, str, n, dp) << endl;
return 0;
}실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.
Maximum length of segment = 12
복잡도 분석
각 시작 위치에서 최대 n개의 끝점을 시도하므로 시간 복잡도는 O(n²)입니다. dp 배열에 결과를 저장해 동일한 시작 위치에 대한 중복 탐색을 제거하며, 공간 복잡도는 O(n)입니다.