[BOJ/Silver 4] 백준 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 이하이다.

출력

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

예제 입력 1

3
2 3 4

예제 출력 1

26

예제 입력 2

4
1 2 3 4

예제 출력 2

35

예제 입력 3

4
2 3 2 4

예제 출력 3

44

알고리즘 분류

• 수학
• 누적 합

풀이

이 문제랑 똑같은 문제다.

14929번: 귀찮아 (SIB)

누적 합을 구하고, i가 1부터 N까지인 i번째 수와 i+1번째 수부터 N번째 수까지의 합의 곱을 더해준다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
int N;
LL MAP[MAX];
LL Sum[MAX];
LL Answer = 0;

void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> MAP[i];
		Sum[i] = Sum[i - 1] + MAP[i];
	}
}

void Settings() {
	for (int i = 1; i < N; i++) {
		Answer += (Sum[N] - Sum[i]) * MAP[i];
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}