합이 n이 되는 연속 정수 범위를 찾는 C++ 프로그램

숫자 n이 하나 주어졌다고 가정해 봅시다. 우리는 l < r을 만족하면서 l + (l + 1) + ... + (r - 1) + r = n이 성립하는 두 정수 l과 r을 찾아야 합니다.

예를 들어 입력이 n = 25라면, 출력으로 l = -2와 r = 7을 구할 수 있습니다. 실제로 (−2) + (−1) + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 25가 되기 때문입니다. 물론 조건만 충족한다면 다른 답도 가능합니다.

해결 접근 방법

이 문제는 의외로 아주 간단하게 풀 수 있습니다. 핵심은 바로 -(n-1)과 n을 반환하는 것입니다.

-(n-1)과 n을 반환

왜 이 방법이 동작할까요?

그 이유는 다음과 같습니다. -(n-1)부터 (n-1)까지의 모든 정수를 더하면 부호가 반대인 항들이 서로 상쇄되어 합이 0이 됩니다. 여기에 마지막 항인 n을 더하면 전체 합이 정확히 n이 되는 것입니다.

즉, (-24) + (-23) + ... + (-1) + 0 + 1 + ... + 23 + 24 + 25 = 25처럼, 대칭적인 구간 덕분에 중간 항들은 모두 사라지고 n만 남게 됩니다. 따라서 어떤 n이 입력되더라도 이 방식으로 항상 답을 구할 수 있습니다.

C++ 구현 예제

다음 코드를 통해 더 잘 이해해 보겠습니다.

#include<bits/stdc++.h>
using namespace std;

void solve(int n){
    cout << -(n-1) << ", " << n;
}
int main(){
    int n = 25;
    solve(n);
}

입력

25

출력

-24, 25

마무리

이 문제는 겉보기에는 복잡해 보이지만, 음수와 양수가 대칭적으로 상쇄되는 성질을 활용하면 O(1) 시간 복잡도로 즉시 답을 도출할 수 있습니다. 반복문이나 누적 합 계산 없이 한 번의 계산으로 해결되는 패턴이므로, 코딩 테스트나 알고리즘 문제 풀이에서 기억해 두면 매우 유용합니다.