문제 설명
이 문제에서는 두 개의 숫자 L과 R이 주어집니다. 그리고 arr[i] = i × (-1)^i 규칙을 따르는 배열 arr[]가 존재합니다. 우리의 목표는 이 배열에서 인덱스 L부터 R까지의 요소 합을 계산하는 프로그램을 작성하는 것입니다.
다시 말해, 배열의 [L, R] 범위에 속한 요소들의 합을 구해야 합니다. 이 배열의 특징은 인덱스가 짝수일 때 값이 양수(i), 홀수일 때 값이 음수(-i)가 된다는 점입니다. 예를 들어 arr[1] = -1, arr[2] = 2, arr[3] = -3과 같습니다.
예제로 문제 이해하기
입력
L = 2, R = 6
출력
4
설명
arr[] = {-1, 2, -3, 4, -5, 6}
합계 = 2 + (-3) + 4 + (-5) + 6 = 4방법 1: 단순 반복문 접근 (O(n))
가장 직관적인 해결 방법은 L부터 R까지 반복문을 돌면서 짝수 인덱스의 값은 더하고 홀수 인덱스의 값은 빼는 것입니다. 모든 연산이 끝나면 최종 합계를 반환하면 됩니다.
예제 코드
#include <iostream>
#include <math.h>
using namespace std;
int CalcArrSumLtoR(int L, int R) {
int sum = 0;
for (int i = L; i <= R; i++){
sum += (i * pow((-1), i));
}
return sum;
}
int main() {
int L = 3, R = 15;
cout<<"Sum of elements of array from index "<<L<<" to "<<R<<" is "<<CalcArrSumLtoR(L, R);
return 0;
}
출력
Sum of elements of array from index 3 to 15 is -9
이 방법은 이해하고 구현하기 쉽다는 장점이 있지만, 범위 내의 모든 요소를 하나씩 순회해야 하므로 시간 복잡도가 O(n)입니다. 따라서 범위가 매우 넓은 경우에는 비효율적일 수 있습니다.
방법 2: 수학 공식을 활용한 효율적 접근 (O(1))
더 효율적인 해결책은 홀수와 짝수의 합에 대한 잘 알려진 수학 공식을 활용하는 것입니다.
- 처음 n개의 홀수의 합 = n × n
- 처음 n개의 짝수의 합 = n × (n + 1)
이 공식들을 이용하면 최종 합계는 다음과 같이 계산할 수 있습니다.
sum = (첫 R개 짝수의 합 − 첫 (L−1)개 짝수의 합) − (첫 R개 홀수의 합 − 첫 (L−1)개 홀수의 합)
여기서 중요한 포인트는 n까지의 범위에는 짝수와 홀수가 각각 약 N/2개씩 존재한다는 것입니다. 즉, R까지의 범위에는 R/2개의 짝수가 있으므로, R/2와 L/2 값을 사용하여 합을 계산할 수 있습니다.
이 방식을 사용하면 반복문 없이 상수 시간 O(1)만에 답을 구할 수 있습니다. 범위가 아무리 커도 즉시 결과를 얻을 수 있어 성능 면에서 압도적으로 유리합니다.
예제 코드
#include <iostream>
using namespace std;
long int findSum(int n, bool isEven) {
long int total = 0;
if(isEven == true){
total = (n) / 2;
return (total * (total+1));
}
else {
total = (n + 1) / 2;
return total * total;
}
}
int CalcArrSumLtoR(int L, int R) {
return (findSum(R, true) - findSum(L - 1, true)) - (findSum(R, false) - findSum(L - 1, false));
}
int main() {
int L = 3, R = 15;
cout<<"Sum of elements of array from index "<<L<<" to "<<R<<" is "<<CalcArrSumLtoR(L, R);
return 0;
}
출력
Sum of elements of array from index 3 to 15 is -9
마무리
단순 반복문을 사용하는 방법은 O(n)의 시간 복잡도를 가지지만, 홀수·짝수의 합 공식을 활용하면 O(1)의 시간 복잡도로 동일한 결과를 얻을 수 있습니다. 코딩 테스트나 대용량 데이터 처리처럼 범위가 큰 상황에서는 수학적 접근 방식을 선택하는 것이 훨씬 효율적입니다.