문제 개요
이 문제에서는 정수 N이 주어지며, 목표는 1² − 2² + 3² − 4² + … 과 같이 부호가 번갈아 나타나는 수열의 n번째 항까지의 합을 구하는 것입니다.
예시를 통해 문제를 이해해 보겠습니다.
입력 : N = 3
출력 : 6
설명 −
1² − 2² + 3² = 1 − 4 + 9 = 6
풀이 방법 1: 반복문 활용
가장 직관적인 해결 방법은 반복문을 사용하는 것입니다. 반복 변수 i를 1부터 n까지 순회하며 다음 규칙을 적용합니다.
- i가 홀수이면 i²를 합에 더합니다.
- i가 짝수이면 i²를 합에서 뺍니다.
반복이 끝난 후 누적된 합을 반환하면 됩니다.
알고리즘
초기화 − sum = 0
- 1단계 − i를 1부터 n까지 반복합니다.
- 1.1단계 − i가 홀수이면(i % 2 != 0), sum += i²
- 1.2단계 − i가 짝수이면(i % 2 == 0), sum -= i²
- 2단계 − sum을 반환합니다.
구현 예제
아래 프로그램은 위 풀이의 동작을 보여줍니다.
#include <iostream>
using namespace std;
int findSumOfSeries(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
if (i % 2 == 0)
sum -= (i*i);
else
sum += (i*i);
}
return sum;
}
int main(void) {
int n = 5;
cout<<"수열의 합은 "<<findSumOfSeries(n);
}
실행 결과
수열의 합은 15
풀이 방법 2: 수학 공식 활용
또 다른 접근 방법은 수열의 합 공식을 이용하는 것입니다. 이 방법은 반복 없이 O(1) 시간에 답을 구할 수 있어 훨씬 효율적입니다.
N이 짝수인 경우
sum = 1² − 2² + 3² − 4² + … + (n−1)² − n²
인접한 두 항씩 묶어 인수분해하면,
sum = (1−2)(1+2) + (3−4)(3+4) + … + ((n−1)−n)((n−1)+n)
sum = (−1)(3) + (−1)(7) + … + (−1)(2n−1)
sum = −(1 + 2 + 3 + … + n)
sum = −n(n+1)/2
N이 홀수인 경우
마지막 항 n²이 양수이므로, 앞의 n−1개 항(짝수 길이 부분)의 결과에 n²을 더하면 됩니다.
sum = [−(n−1)n/2] + n²
sum = (−n² + n + 2n²)/2
sum = n(n+1)/2
즉, n이 짝수일 때는 합이 음수, 홀수일 때는 양수이며, 그 절댓값은 항상 n(n+1)/2라는 규칙을 확인할 수 있습니다.
구현 예제
#include <iostream>
using namespace std;
int findSumOfSeries(int n) {
int sum = 0;
if (n % 2 == 0)
sum = (-1) * (n * (n + 1)) / 2;
else
sum = (n * (n + 1)) / 2;
return sum;
}
int main(void) {
int n = 5;
cout<<"수열의 합은 "<<findSumOfSeries(n);
}
실행 결과
수열의 합은 15
마무리
반복문 풀이는 시간 복잡도가 O(n)으로 이해하기 쉬운 반면, 공식 풀이는 O(1)로 아주 큰 n에도 즉시 답을 구할 수 있다는 장점이 있습니다. 입력 크기와 요구 사항에 따라 두 방법 중 적절한 것을 선택해 사용하면 됩니다.