문제

N개의 정수 중 서로 다른 위치의 두 수를 뽑는 모든 경우의 두 수의 곱의 합을 구하라.

예를 들어 N = 3이고 주어진 정수가 2, 3, 4일 때, 두 수를 뽑는 모든 경우는 (2, 3), (2, 4), (3, 4)이며 이때 각각의 곱은 6, 8, 12이다. 따라서 총합은 26이다.

입력

첫 번째 줄에는 입력 받을 정수의 개수 N(2 ≤ N ≤ 100,000)
두 번째 줄에는 N 개의 정수가 주어진다. 이때 입력 받는 정수들의 범위는 0이상 10,000 이하이다.

출력

모든 경우의 곱의 합을 출력한다.

예제 입력

3
2 3 4

예제 출력

26

내가 했던 풀이 방법

(1, 2, 3, 4)가 주어졌을 때의 합은 (1 * 2) + (1 * 3) + (1 * 4) + (2 * 3) + (2 * 4) + (3 * 4)이게 된다. 이를 다른 식으로 바꾼다면 1*(2+3+4) + 2*(3+4) + 3*(4)가 된다.

모든 num의 합을 더해준다음 1부터 순서대로 앞의 수를 sum에서 제거해주면서 제거해준 값을 곱해주면 된다. 즉 1+2+3+4를 구한다음 for문을 이용해 맨 앞 수부터 sum에서 제거해준다. (2+3+4)를 제거한 수 1로 곱해주면 1*(2+3+4)가 된다. 이를 반복해서 sum에서 다음 2를 제거해주고, (3+4)에 2를 곱해준다. 이를 반복해주면 된다.

코드

const fs = require('fs');
let [N, num] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

N = Number(N);
num = num.trim().split(' ').map(BigInt);

let sum = 0n;
for (let i = 0; i < N; i++) {
  sum += num[i];
}

let answer = 0n;
for (let i = 0; i < N; i++) {
  sum -= num[i];
  answer += num[i] * sum;
}

console.log(answer.toString());

회고

도대체 사람들은 이런 방법들을 어떻게 떠올릴 수 있는 걸까...