Post

[Programmers] #181935 - 홀짝에 따라 다른 값 반환하기 [Java][C++][Python]

[Programmers] #181935 - 홀짝에 따라 다른 값 반환하기 [Java][C++][Python]

문제 링크


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

This post is licensed under CC BY 4.0 by the author.