문제 개요
이 문제에서는 양의 정수 N이 주어지며, 합이 N과 같아지는 모든 연속된 숫자 수열을 찾아 출력해야 합니다.
예시를 통해 문제를 이해해 보겠습니다.
입력: N = 15
출력: 1 2 3 4 5
7 8
방법 1: 단순 반복 탐색
가장 직관적인 해결 방법은 시작점을 1부터 N/2까지 하나씩 옮겨 가면서, 각 시작점에서 연속된 숫자를 차례대로 더해 보는 것입니다. 중간에 합이 N과 같아지면 그 수열을 출력하고, N을 초과하면 다음 시작점으로 넘어갑니다.
예제 코드
#include<iostream>
using namespace std;
void printConsecutiveSum(int N){
int start = 1, end = (N+1)/2;
while (start < end){
int sum = 0;
for (int i = start; i <= end; i++){
sum = sum + i;
if (sum == N){
for (int j = start; j <= i; j++)
cout<<j<<" ";
cout<<endl;
break;
}
if (sum > N)
break;
}
sum = 0;
start++;
}
}
int main(){
int N = 25;
cout<<"합이 "<<N<<"이 되는 연속된 숫자 수열:\n";
printConsecutiveSum(N);
return 0;
}
출력 결과
N이 25일 때, 합이 25가 되는 연속된 숫자 수열은 다음과 같습니다.
3 4 5 6 7
12 13
이 방법은 구현이 매우 쉽다는 장점이 있지만, 시작점이 바뀔 때마다 처음부터 다시 더해야 하므로 시간 복잡도가 O(N²)에 가까워 효율성이 떨어집니다.
방법 2: 슬라이딩 윈도우(투 포인터) 기법
보다 최적화된 방법은 누적합을 상태로 유지하면서 구간의 양 끝(start, end)을 동적으로 조절하는 슬라이딩 윈도우 기법입니다. 동작 원리는 다음과 같습니다.
- 현재 합이 N보다 작으면: 윈도우의 끝(end)을 한 칸 확장하고 새 숫자를 더합니다.
- 현재 합이 N보다 크면: 윈도우의 시작(start) 값을 합에서 빼고 시작점을 한 칸 앞으로 이동합니다.
- 현재 합이 N과 같으면: 해당 구간을 출력한 뒤, 시작 값을 빼고 다음 구간을 탐색합니다.
이 방식은 매번 처음부터 재계산하지 않으므로 시간 복잡도를 O(N) 수준으로 크게 줄일 수 있습니다.
예제 코드
#include <iostream>
using namespace std;
void printConsecutiveSum(int N){
int start = 1, end = 1;
int sum = 1;
while (start <= N/2){
if (sum < N){
end += 1;
sum += end;
}
else if (sum > N){
sum -= start;
start += 1;
}
else if (sum == N){
for (int i = start; i <= end; ++i)
cout<<i<<" ";
cout<<endl;
sum -= start;
start += 1;
}
}
}
int main(){
int N = 25;
cout<<"합이 "<<N<<"이 되는 연속된 숫자 수열:\n";
printConsecutiveSum(N);
return 0;
}
출력 결과
N이 25일 때의 실행 결과는 첫 번째 방법과 동일합니다.
3 4 5 6 7
12 13
마무리
두 방법 모두 동일한 결과를 출력하지만, 슬라이딩 윈도우 기법은 누적합을 활용해 불필요한 반복 계산을 제거하므로 입력 값이 커질수록 성능 차이가 현저하게 벌어집니다. 실전 코딩 테스트나 대용량 데이터 처리에서는 두 번째 방법을 사용하는 것이 바람직합니다.