[C++] 백준 11059번 크리 문자열 - 문자열, 누적합 (String, Prefix Sum)

🔍 문제 요약

• 문제 링크: 백준 11059번 - 크리 문자열
• 주요 태그: 문자열, 누적합, 슬라이딩 윈도우, 브루트포스 최적화

---

💡 문제 분석

• 숫자로 이루어진 문자열 S가 주어진다.
• 연속된 부분 문자열 중 길이가 짝수이고,
  앞 절반의 합 == 뒤 절반의 합인 것을 '크리 문자열'이라 정의한다.
• 모든 크리 문자열 중 가장 긴 길이를 출력해야 한다.

---

🔑 아이디어

• 모든 짝수 길이의 부분 문자열을 확인하며,
  각 부분을 앞/뒤 절반으로 나누고, 그 합을 비교해야 한다.
• 부분합을 반복해서 계산하면 O(n³) 시간복잡도가 발생하므로,
  누적합(Prefix Sum) 기법을 활용해 각 구간의 합을 O(1)로 계산하도록 최적화한다.

---

🧩 풀이 전략

1. 문자열 S의 각 숫자를 정수형으로 바꾼 뒤 누적합 배열을 만든다.
   • prefix[i] = S[0] + S[1] + ... + S[i-1]
2. 문자열 길이 len을 큰 값부터 짝수만 탐색한다.
   • 길이 len을 고정하고 슬라이딩 윈도우처럼 모든 시작 위치 i에 대해:
     • 앞 절반의 합: prefix[i + len/2] - prefix[i]
     • 뒤 절반의 합: prefix[i + len] - prefix[i + len/2]
     • 두 합이 같으면, 현재 길이가 가능한 최대 크리 문자열이다.
3. 가장 먼저 발견된 크리 문자열의 길이를 반환하면 그것이 최대 길이.

---

📦 예제 입력 & 출력

• 입력:

  67896789

• 출력:

  8

• 입력:

  6789789

• 출력:

  6

---

🖥️ 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string n;
    cin >> n;

    int size = n.size();
    int sum[1001];
    sum[0] = 0;

    // 누적합 계산
    for (int i = 1; i <= size; i++) {
        sum[i] = (n[i - 1] - '0') + sum[i - 1];
    }

    int maxLen = 0;
    for (int len = 2; len <= size; len += 2) {
        for (int i = 0; i + len <= size; i++) {
            int leftSum = sum[i + len / 2] - sum[i];
            int rightSum = sum[i + len] - sum[i + len / 2];
            if (leftSum == rightSum) {
                maxLen = max(maxLen, len);
            }
        }
    }

    cout << maxLen;
    return 0;
}

---

✅ 검증 및 테스트

• 다양한 문자열에 대해 슬라이딩 윈도우 + 누적합 방식으로 정확히 처리됨
• 입력의 최대 길이 1000에 대해 O(n²) → 100만 연산이므로 충분히 빠름

---

⏱️ 시간복잡도

• 누적합 계산: O(n)
• 이중 루프: O(n²) (짝수 길이 * 시작 인덱스 슬라이딩)
• 총 시간복잡도: O(n²) → n ≤ 1000 이므로 통과 가능

---

✨ 결론

• 이 문제는 단순하게 생각하면 브루트포스처럼 보이지만,
  누적합(Prefix Sum)을 도입하면 연산을 O(n³) → O(n²)로 줄일 수 있다.
• 앞/뒤 절반의 합을 비교하는 문제에서 누적합을 활용하면 시간도 줄고, 코드가 훨씬 간결해진다.
• 부분합을 자주 계산한다면 누적합을 고려할 것!

---