문제 링크
1. 아이디어
n이 홀수면 n 이하의 홀수를 모두 더하고, 짝수면 n 이하의 짝수의 제곱을 모두 더한 값을 반환하면 되는 문제다. 가장 직관적인 방법은 홀짝을 나눈 뒤 2씩 건너뛰며 순회해서 합을 누적하는 것이다.
이 합은 닫힌 형태의 공식으로 $O(1)$의 시간복잡도로 구할 수도 있다. n이 홀수라면 1부터 n까지의 홀수는 $1, 3, 5, \dots, n$으로 총 $k = (n + 1) / 2$개인데, 1부터 시작하는 연속된 홀수 $k$개의 합은 항상 $k$의 제곱이 된다(홀수를 한 겹씩 덧붙일 때마다 정사각형이 하나씩 커지는 것과 같은 성질). 따라서 결과는 $k^2$이다.
n이 짝수라면 2부터 n까지의 짝수는 $2, 4, \dots, n$으로 총 $k = n / 2$개이고, $i$번째 짝수는 $2i$이므로 그 제곱의 합은 $\sum_{i=1}^{k} (2i)^2 = 4 \sum_{i=1}^{k} i^2$이다. 자연수 제곱합 공식 $\sum_{i=1}^{k} i^2 = k(k + 1)(2k + 1) / 6$을 대입하면 결과는 $2k(k + 1)(2k + 1) / 3$으로 정리된다.
2. 복잡도
| 접근 | 시간 | 공간 |
|---|
| 반복 합산 | $O(N)$ | $O(1)$ |
| 합 공식 | $O(1)$ | $O(1)$ |
($N$ = 입력값 n)
3. 코드
풀이 1: 반복 합산 [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int solution(int n) {
if (n % 2 != 0) {
int sum = 0;
for (int i = 1; i <= n; i += 2) {
sum += i;
}
return sum;
} else {
int sum = 0;
for (int i = 2; i <= n; i += 2) {
sum += i * i;
}
return sum;
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <bits/stdc++.h>
using namespace std;
int solution(int n) {
if (n % 2) {
int sum = 0;
for (int i = 1; i <= n; i += 2) {
sum += i;
}
return sum;
} else {
int sum = 0;
for (int i = 2; i <= n; i += 2) {
sum += i * i;
}
return sum;
}
}
|
1
2
3
4
5
| def solution(n):
if n % 2:
return sum(range(1, n + 1, 2))
else:
return sum(i * i for i in range(2, n + 1, 2))
|
풀이 2: 합 공식 [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int solution(int n) {
if (n % 2 != 0) {
int k = (n + 1) / 2;
return k * k;
} else {
int k = n / 2;
return 2 * k * (k + 1) * (2 * k + 1) / 3;
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| #include <bits/stdc++.h>
using namespace std;
int solution(int n) {
if (n % 2) {
int k = (n + 1) / 2;
return k * k;
} else {
int k = n / 2;
return 2 * k * (k + 1) * (2 * k + 1) / 3;
}
}
|
1
2
3
4
5
6
7
| def solution(n):
if n % 2:
k = (n + 1) // 2
return k * k
else:
k = n // 2
return 2 * k * (k + 1) * (2 * k + 1) // 3
|