이 글에서는 C++을 사용해 k^m(m ≥ 0) 형태의 합을 갖는 부분 배열(subarray)의 개수를 구하는 문제를 자세히 다뤄보겠습니다. 배열 arr[]와 정수 K가 주어졌을 때, 합이 K^m(m은 0 이상의 정수) 꼴인 부분 배열이 몇 개 있는지 찾아야 합니다. 즉, 부분 배열의 합이 K의 음수가 아닌 거듭제곱 값과 일치하는 경우의 수를 세는 것이 목표입니다.
문제 예시
입력: arr[] = { 2, 2, 2, 2 }, K = 2
출력: 8
다음 인덱스 구간의 부분 배열들이 조건을 만족합니다:
[1, 1], [2, 2], [3, 3], [4, 4], [1, 2],
[2, 3], [3, 4], [1, 4]
입력: arr[] = { 3, -6, -3, 12 }, K = -3
출력: 3이 문제를 해결하는 대표적인 방법은 크게 두 가지입니다.
방법 1: 브루트 포스(Brute Force)
가장 직관적인 접근 방식으로, 가능한 모든 부분 배열을 하나씩 살펴보며 그 합이 K의 거듭제곱(0승 = 1 포함)인지 검사하고, 조건을 만족하면 카운트를 1씩 증가시킵니다.
예제 코드
#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int main(){
int arr[] = {2, 2, 2, 2}; // 주어진 배열
int k = 2; // 주어진 정수
int n = sizeof(arr) / sizeof(arr[0]); // 배열의 크기
int answer = 0; // 카운터 변수
for(int i = 0; i < n; i++){
int sum = 0;
for(int j = i; j < n; j++){ // 모든 부분 배열을 생성하는 반복문
sum += arr[j];
int b = 1;
while(b < MAX && sum > b) // k^m의 최댓값은 10^6으로 가정
b *= k;
if(b == sum) // b == sum이면 카운트 증가
answer++;
}
}
cout << answer << "\n";
}실행 결과
8
이 방법은 구현이 간단하지만 시간 복잡도가 O(N² · log K)(N은 배열의 크기, K는 주어진 정수)로 비효율적입니다. 제약 조건이 커지면 연산 시간이 급격히 늘어나기 때문에, 더 큰 입력에서도 원활하게 동작하는 다른 접근 방식이 필요합니다.
방법 2: 효율적인 접근 (접두사 합 + 맵)
이 방법에서는 접두사 합(prefix sum)과 맵(map)을 활용해 연산량을 획기적으로 줄입니다. 핵심 아이디어는 다음과 같습니다. 구간 [i+1, j]의 합은 prefix_sum[j] − prefix_sum[i]이므로, 어떤 거듭제곱 b = k^m에 대해 prefix_sum[j] − prefix_sum[i] = b가 되는 쌍의 개수를 세면 됩니다. 배열을 뒤에서부터 순회하면서 맵에 이미 등장한 접두사 합의 빈도를 저장하고, 현재 접두사 합에 b를 더한 값이 맵에 존재하는지 확인하며 답을 누적합니다.
K가 1이면 거듭제곱 값이 항상 1로 고정되고, K가 −1이면 1과 −1이 번갈아 나타나므로 무한 루프를 방지하기 위해 이 두 경우는 별도로 처리합니다. 또한 문제의 제약에 따라 10^6을 초과하는 거듭제곱은 검사하지 않습니다.
예제 코드
#include <bits/stdc++.h>
#define ll long long
#define MAX 1000000
using namespace std;
int main(){
int arr[] = {2, 2, 2, 2}; // 주어진 배열
int n = sizeof(arr) / sizeof(arr[0]); // 배열의 크기
int k = 2; // 주어진 정수
ll prefix_sum[MAX];
prefix_sum[0] = 0;
partial_sum(arr, arr + n, prefix_sum + 1); // 접두사 합 배열 생성
ll sum;
if (k == 1){
// k가 1인 경우는 별도로 처리
sum = 0;
map<ll, int> m;
for (int i = n; i >= 0; i--){
// m[a+b] = c이면 현재 합에 c를 더함
if (m.find(prefix_sum[i] + 1) != m.end())
sum += m[prefix_sum[i] + 1];
// 접두사 합의 개수 증가
m[prefix_sum[i]]++;
}
cout << sum << "\n";
}
else if (k == -1){
// k가 -1인 경우도 별도로 처리
sum = 0;
map<ll, int> m;
for (int i = n; i >= 0; i--){
// m[a+b] = c이면 현재 합에 c를 더함
if (m.find(prefix_sum[i] + 1) != m.end())
sum += m[prefix_sum[i] + 1];
if (m.find(prefix_sum[i] - 1) != m.end())
sum += m[prefix_sum[i] - 1];
// 접두사 합의 개수 증가
m[prefix_sum[i]]++;
}
cout << sum << "\n";
}
else{
sum = 0;
ll b;
map<ll, int> m;
for (int i = n; i >= 0; i--){
b = 1;
while (b < MAX){ // 10^6을 넘는 값은 검사하지 않음
// m[a+b] = c이면 현재 합에 c를 더함
if (m.find(prefix_sum[i] + b) != m.end())
sum += m[prefix_sum[i] + b];
b *= k;
}
m[prefix_sum[i]]++;
}
cout << sum << "\n";
}
return 0;
}실행 결과
8
마무리
이번 글에서는 합이 k^m(m ≥ 0) 형태인 부분 배열의 개수를 O(n · log k · log n) 시간 복잡도로 구하는 방법을 알아보았습니다. 단순한 브루트 포스부터 접두사 합과 맵을 결합한 효율적인 풀이까지 전체 과정을 C++ 코드와 함께 살펴보았습니다. 같은 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 문제 해결에 도움이 되기를 바랍니다.