[Programmers] #120831 - 짝수의 합 [Java][C++][Python]

문제 링크

---

1. 아이디어

정수 n이 주어질 때, n 이하의 짝수를 모두 더한 값을 구하는 문제다.

가장 직관적인 방법은 2부터 n까지 2씩 증가시키면서 값을 그대로 누적하는 것이다. $O(N)$의 시간복잡도가 소요되지만 n이 크지 않아서 충분한 방법이다.

두 번째 방법은 $O(1)$의 시간복잡도로 구하는 방법으로, 짝수의 합은 등차수열의 합 공식으로도 바로 구할 수 있다. n 이하의 짝수는 $2, 4, \ldots, 2k$ ($k = \lfloor n / 2 \rfloor$) 형태의 등차수열이므로, 첫째항과 마지막항의 합에 항의 개수를 곱해 $2$로 나누는 공식 $\dfrac{(2 + 2k) \times k}{2}$, 정리하면 $k(k + 1)$로 반복문 없이 한 번에 계산할 수 있다.

---

2. 복잡도

접근	시간	공간
반복 합산	$O(N)$	$O(1)$
등차수열 합 공식	$O(1)$	$O(1)$

($N$ = 입력값 n)

---

3. 코드

풀이 1: 반복 합산 [Java][C++][Python]

class Solution {
    public int solution(int n) {
        int sum = 0;
        for (int i = 2; i <= n; i += 2) {
            sum += i;
        }

        return sum;
    }
}

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

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

    return sum;
}

def solution(n):
    return sum(range(2, n + 1, 2))

---

풀이 2: 등차수열 합 공식 [Java][C++][Python]

class Solution {
    public int solution(int n) {
        int k = n / 2;
        return k * (k + 1);
    }
}

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

int solution(int n) {
    int k = n / 2;
    return k * (k + 1);
}

def solution(n):
    k = n // 2
    return k * (k + 1)

---