여기서 우리는 숫자가 동일한 합을 갖는 하나 이상의 세그먼트로 분할될 수 있는지 여부를 확인할 수 있는 프로그램을 볼 것입니다. 숫자가 74325와 같다고 가정하면 이것은 세 부분으로 분할될 수 있습니다 (7), (4, 3), (2, 5), 모두 동일한 um 값입니다.
이 문제를 해결하려면 다음 단계를 따라야 합니다.
- 숫자를 문자열로 사용
- 배열을 사용하여 배열의 접두사 합계를 보유
- 이제 두 번째 요소에서 마지막 요소로 이동하고 첫 번째 세그먼트는 0에서 i-1까지이며 합계는 prefix_sum[i - 1]에 위치합니다.
- 1에서 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