[TIL #7] 짝수의 합 구하기

심플한 등차수열 문제.

정수 n이 주어질 때, n 이하의 모든 짝수를 더한 수를 리턴하면 된다.

 

단순하게 아래와 같이 할 수도 있다.

int solution(int n) {
    int answer = 0;
    
    for(int i = 0; i <= n; i += 2)
        answer += i;
    
    return answer;
}

하지만 이건 뭔가 아쉽지 않은가?

좀 더 괜찮은 답을 찾아보자.

 

 

등차수열

이 문제는 2부터 시작해서 2의 공차를 가지는 등차수열의 합을 구하는 문제이다.

간단하게 말해서 짝수의 합.

 

짝수 수열 $2, 4, 6, \ldots, 2k$의 합을 구하는 공식은 다음과 같다.

\[ S = 2 + 4 + 6 + \ldots + 2k \]

 

이를 일반화하면 다음과 같이 나타낼 수 있다.

$$S = 2 \times (1 + 2 + 3 + \ldots + k)$$
여기서 $k$는 $n$을 2로 나눈 몫이다.

 

1부터 $k$까지의 합은 $\frac{k(k + 1)}{2}$이다. 이를 짝수로 변환하면
$$S = 2 \times \frac{k(k + 1)}{2} = k(k + 1)$$

 

따라서, 주어진 $n$ 이하의 짝수의 합은:
$$S = k(k + 1)$$
여기서 $k = \left\lfloor \frac{n}{2} \right\rfloor$

 

 

그럼 이걸 코드로 옮기면 다음과 같다.

#include <cmath>

int solution(int n) {
    int cnt = floor(n / 2);
    int answer = cnt * (cnt + 1);
    return answer;
}

 

 

새삼 알고리즘이란 이런 것이었지 하는 생각이 든다.