solved.ac Grand Arena #2

풀이 1

문제에서 주어진대로 반복문을 통해 구현합니다. 시간복잡도는 $\mathcal O (N)$ 입니다.

코드 (C++)

#include <iostream>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int sum_1 = 0, sum_3 = 0;
    for (int i = 1; i <= N; i++)
    {
        sum_1 += i;
        sum_3 += i * i * i;
    }
    cout << sum_1 << endl;
    cout << sum_1 * sum_1 << endl;
    cout << sum_3 << endl;
}

코드 (Python)

def main():
    N = int(input())
    print(sum(range(1, N+1)))
    print(sum(range(1, N+1))**2)
    print(sum(i**3 for i in range(1, N+1)))


if __name__ == '__main__':
    main()

풀이 2

$1+2+\cdots+N = \frac{N(N+1)}{2}$ 가 성립합니다. 또한, $1^3 + 2^3 + \cdots + N^3 = (1+2+\cdots+N)^2 = {\left(\frac{N(N+1)}{2}\right)}^2$ 이 성립합니다. 시간복잡도는 $\mathcal O (1)$ 입니다.

코드 (C++)

#include <iostream>
using namespace std;

int main()
{
    int N;
    cin >> N;
    cout << N * (N + 1) / 2 << endl;
    cout << (N * (N + 1) / 2) * (N * (N + 1) / 2) << endl;
    cout << (N * (N + 1) / 2) * (N * (N + 1) / 2) << endl;
}

코드 (Python)

def main():
    N = int(input())
    print(N * (N + 1) // 2)
    print((N * (N + 1) // 2) ** 2)
    print((N * (N + 1) // 2) ** 2)


if __name__ == '__main__':
    main()

증명

우선, $1+2+\cdots+N = \frac{N(N+1)}{2}$ 를 증명하기 위해 $2 \times (1 + 2+ \cdots + N)$ 를 계산해봅시다.

$(1+2+\cdots+N)$ 두 개를 더할 때 하나는 그대로, 하나는 뒤집어서 더합시다. 이후 각 수를 살펴보면 $1$ 과 $N$ 을 합쳐서 $N+1$ , $2$ 와 $N-1$ 을 합쳐서 $N+1$ , $\cdots$ , $N$ 과 $1$ 을 합쳐서 $N+1$ 이 되기 때문에 $N+1$ 을 총 $N$ 개 합한 $N(N+1)$ 과 같게 됩니다.

이를 수식으로 표현하면 다음과 같습니다.

\begin{align*} & \ 2 \times (1 + 2 + \cdots + N) \\ = & \ (1 + 2 + \cdots + N) + (N + (N-1) + \cdots + 1) \\ = & \ ((1+N) + (2+(N-1)) + \cdots + (N+1)) \\ = & \ ((N+1) + (N+1) + \cdots+ (N+1)) \\ = & \ N(N+1) \end{align*}

$1+2+\cdots+N = \frac{N(N+1)}{2}의 시각적 증명$

이제 조금 더 난이도가 있는 $(1+ 2+ \cdots + N)^2 = 1^3 + 2^3 + \cdots + N^3$ 을 증명해봅시다. 양변에 있는 두 식이 $N=1$ 일 때 같은 값을 가지고 $N=i-1$ 와 $N=i$ 일때 차이가 같아서, 결국 두 식이 같다는 것을 증명할 것입니다. $N = 1$ 일 때는 두 식의 값이 모두 $1$ 로 같습니다. 이제, 두 식의 차이에 대해 살펴봅시다.

이제, $(1+2+ \cdots+N)^2$ 의 $N=i-1$ 과 $N=i$ 일 때의 차는 다음과 같습니다. $a^2-b^2 = (a-b)(a+b)$ 임을 이용합시다.

\begin{align*} & \ (1+2+\cdots+i)^2 - (1+2+\cdots+(i-1)^2) \\ = & \ \left(\frac{i(i+1)}{2}\right)^2 - \left(\frac{i(i-1)}{2}\right)^2 \\ = & \ \left(\frac{i(i+1)}{2} - \frac{i(i-1)}{2}\right) \times \left(\frac{i(i+1)}{2} + \frac{i(i-1)}{2}\right) \\ = & \ \left(\frac{i((i+1)-(i-1))}{2}\right) \times \left(\frac{i((i+1)+(i-1))}{2}\right) \\ = & \ \left(\frac{i \times 2}{2} \right) \times \left(\frac{i \times 2i}{2} \right) \\ = & \ i \times i^2 = i^3 \end{align*}

$1^3 + 2^3 + \cdots + (i-1)^3$ 과 $1^3 + 2^3 + \cdots + i^3$ 의 차이도 $i^3$ 이므로, 두 식이 결국 같은 값임을 알 수 있습니다.

이 식을 시각적으로 증명하는 방법도 있습니다.

$(1+2+\cdots+N)^2 = 1^3+2^3+\cdots+N^3의 시각적 증명$