[BOJ 23827] 백준 23827번 - 수열 (Easy)

		SASA Programming Contest 2021 풀이
A		[BOJ 23825] SASA 모형을 만들어보자
B		[BOJ 23826] 와이파이
C1		[BOJ 23827] 수열 (Easy)
C2		[BOJ 23828] 수열 (Hard)
D		[BOJ 23829] 인문예술탐사주간
E		[BOJ 23830] 제기차기
F		[BOJ 23831] 나 퇴사임?
G		[BOJ 23832] 서로소 그래프
J1		[BOJ 23835] 어떤 우유의 배달목록 (Easy)

1. 문제

$23827$. 수열 (Easy) (SASA Programming Contest 2021 Open Contest C1번)

백준 23827번 - 수열 (Easy) (https://www.acmicpc.net/problem/23827)

2. 풀이

수가 $a, b, c, d$라고 하면, 이렇게 계산할 수 있다. $a\times b+a\times c+a\times d+b\times c+b\times d+c\times d $ $ =a\times (b+c+d)+b\times (c+d)+c\times (d)$

이를 일반화해서, $a_1$부터 $a_N$까지 있다고 가정하면, 다음과 같이 된다. $a_1\times (a_2\sim a_N까지의 합)$ $+\;a_2\times (a_3\sim a_N까지의 합)$ $+\;a_3\times (a_4\sim a_N까지의 합)$ $+…+\;a_{N-1}\times (a_N\sim a_N까지의 합)$

미리 모든 수의 합을 계산해 놓음으로써 $a_i\sim a_N$의 합을 효율적으로 구할 수 있다. 모든 수의 합의 최댓값은 $500,000*500,000$ $=250,000,000,000$ 이므로 long long 범위$(10^{18})$안에 들어 계산이 가능하다.

3. 채점 결과

4. 회고

.

5. 코드