이 글에서는 하나의 큰 숫자를 합이 같은 둘 이상의 구간(세그먼트)으로 나눌 수 있는지 판별하는 C++ 프로그램을 살펴봅니다.
예를 들어 숫자가 74325라고 가정해 보겠습니다. 이 숫자는 (7), (4, 3), (2, 5)의 세 부분으로 나눌 수 있으며, 각 구간의 합은 모두 7로 동일합니다. 따라서 이 숫자는 조건을 만족하는 숫자입니다.
문제 해결 접근 방식
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 숫자를 문자열 형태로 입력받습니다.
- 배열을 사용하여 각 자릿수의 누적합(prefix sum)을 저장합니다.
- 두 번째 요소부터 마지막 요소까지 탐색하며, 첫 번째 구간은 0부터 i-1까지이고 그 합은
prefix_sum[i - 1]에 저장됩니다. - 또 다른 변수를 사용해 인덱스 i부터 n까지 순회하면서 구간의 합을 계속 더해갑니다.
- 어느 시점에서 구간의 합이
prefix_sum[i - 1]과 같아지면, 해당 구간의 합이 첫 번째 구간과 같다는 의미입니다. - 구간 합을 0으로 다시 초기화한 후 포인터를 계속 앞으로 이동시킵니다.
- 중간에 구간 합이
prefix_sum[i - 1]보다 커지면 반복문을 종료합니다. 더 이상 같은 합으로 나눌 수 없기 때문입니다. - 마지막 지점까지 도달했을 때 마지막 구간의 합이 첫 번째 구간의 합과 같다면, 해당 숫자는 합이 같은 여러 구간으로 나눌 수 있는 것입니다.
예제 코드
#include <iostream>
using namespace std;
bool canBeSegmented(string str) {
int n = str.length();
int prefix_sum[n];
prefix_sum[0] = str[0] - '0';
for (int i = 1; i < n; i++) {
prefix_sum[i] = prefix_sum[i - 1] + (str[i] - '0');
}
for (int i = 1; i <= n - 1; i++) {
int sum = prefix_sum[i - 1];
int prev_sum = 0;
int it = i;
bool flag = false;
while (it < n) {
prev_sum += str[it] - '0';
if (prev_sum == sum) {
prev_sum = 0;
flag = true;
} else if (prev_sum > sum) {
break;
}
it++;
}
if (prev_sum == 0 && it == n && flag) {
return true;
}
}
return false;
}
int main() {
string s = "74325";
if (canBeSegmented(s))
cout << "Yes, This can be segmented into more than two segments";
else
cout << "No, This can not be segmented into more than two segments";
}실행 결과
Yes, This can be segmented into more than two segments
복잡도 분석
위 알고리즘은 모든 가능한 첫 번째 구간의 끝점에 대해 문자열 전체를 한 번씩 순회하므로, 시간 복잡도는 O(n²)입니다. 누적합을 저장하기 위해 길이 n의 배열을 사용하므로 공간 복잡도는 O(n)입니다.
숫자를 일반적인 정수형(int, long long)으로 다루면 자릿수 제한이 있지만, 위 코드처럼 문자열로 처리하면 자릿수와 무관하게 매우 큰 수에 대해서도 동일한 방식으로 판별할 수 있다는 점이 이 접근 방식의 장점입니다.