-
[13900] 순서쌍의 곱의 합BOJ 2022. 4. 27. 12:06
https://www.acmicpc.net/problem/13900
13900번: 순서쌍의 곱의 합
첫 번째 줄에는 입력 받을 정수의 개수 N(2 ≤ N ≤ 100,000) 두 번째 줄에는 N 개의 정수가 주어진다. 이때 입력 받는 정수들의 범위는 0이상 10,000 이하이다.
www.acmicpc.net
예제 1은 (2*3) + (2+3)*4,
예제 2는 (1*2) + (1+2)*3 + (1+2+3)*4..와 같은 방식으로 계산하자.
누적합을 구하고, a[1]부터 참조하여 식을 만들어주었다.
#include <bits/stdc++.h>using namespace std;#ifdef ONLINE_JUDGEconstexpr bool local = false;#elseconstexpr bool local = true;#endifusing ll = long long;using pi = pair<ll, ll>;ll n, ans, a[100001], p[100001];int main(void) {if (!local) ios_base::sync_with_stdio(0), cin.tie(0);cin >> n;ll i;for (i = 0; i < n; i++) cin >> a[i];p[0] = a[0];for (i = 1; i < n; i++) p[i] = p[i - 1] + a[i];for (i = 1; i < n; i++) ans += (p[i] - a[i]) * a[i];cout << ans;return 0;}
'BOJ' 카테고리의 다른 글
[24445] 알고리즘 수업 - 너비 우선 탐색 2 (0) 2022.05.02 [15967] 에바쿰 (0) 2022.05.02 [2784] 가로 세로 퍼즐 (0) 2022.04.27 [1107] 리모컨 (0) 2022.04.25 [14500] 테트로미노 (0) 2022.04.22