문제 링크
1. 아이디어
$n$이 홀수이면 $n$ 이하의 홀수를 모두 더하고, 짝수이면 $n$ 이하의 짝수를 제곱해서 모두 더한다. $n \le 100$이라 2씩 건너뛰며 직접 더해도 충분하다.
항을 일일이 더하지 않고 합 공식으로 한 번에 구할 수도 있다. $n$이 홀수이면 $n$ 이하의 홀수는 $k = (n + 1) / 2$개이고 처음 $k$개의 홀수의 합은 $k^2$이다. $n$이 짝수이면 $k = n / 2$라 할 때 구할 값은 $2, 4, \dots, 2k$의 제곱합이다. 제곱합 공식 $\sum_{i=1}^{k} i^2 = \dfrac{k(k + 1)(2k + 1)}{6}$을 쓰면 $\sum_{i=1}^{k} (2i)^2 = 4 \sum_{i=1}^{k} i^2 = \dfrac{2k(k + 1)(2k + 1)}{3}$이다. 분자 $2k(k + 1)(2k + 1)$은 $\sum_{i=1}^{k} i^2$의 12배라 항상 3으로 나누어떨어지므로, 곱을 모두 한 뒤 마지막에 나누어도 정수 나눗셈이 정확하다.
2. 코드
풀이 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))
|
range의 세 번째 인자로 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
|