[백준 13900] 순서쌍의 곱의 합 (C++)

https://www.acmicpc.net/problem/13900

13900번: 순서쌍의 곱의 합

 

문제

---

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 이하이다.

 

출력

---

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

 

문제 풀이

---

누적합을 이용한 문제.

N이 4개이고 각각을 a, b, c, d라 가정해보자. 그러면 우리가 구하는 값은 a*b+a*c+a*d+b*c+b*d+c*d이고, 정리하면 a(b+c+d)+b(c+d)+c*d임을 알 수 있다.

즉, 0부터 i-1번째 배열까지 i번째 배열의 값* (i+1번째부터 N-1번째를 모두 더한 값)을 구해 모두 더해주면 답이 된다. 누적합으로 전체 합을 구한 다음 i번째 배열까지의 값을 빼주면 (i+1번째부터 N-1번째를 모두 더한 값)을 구할 수 있다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int* arr = new int[N];
	long long* sums = new long long[N + 1];
	long long answer = 0;
	sums[0] = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		sums[i + 1] = sums[i] + arr[i];
	}
	for (int i = 0; i < N - 1; i++)
	{
		answer += arr[i] * (sums[N] - sums[i + 1]);
	}
	cout << answer << "\n";
	return 0;
}