백준 13900 순서쌍의 곱의 합

문제 URL : https://www.acmicpc.net/problem/13900

13900번: 순서쌍의 곱의 합

 

문제 접근법 : 수학을 이용해야합니다.

예를들어 a b c d e f 가 있을때 이경우의 수들을 생각해보면

손으로 써보시면 ab, ac ,ad, ae ,af  ,bc ,bd ... ef 까지와서 전부

합의 일반항을 구해보면

a(b+c+d+e+f) + b(c+d+e+f) + c(d+e+f) + d(e+f) + ef 가됩니다. 규칙이 보이시나요?

첫번째 인덱스 a는 그뒤의 합인 b~f까지의 합에서 a를 곱하면되고

두번째 인덱스 b는 그뒤인 c~f까지의 합

마지막은 e는 f하나가 마지막이니 f만 곱해서 전부 다 더해주면됩니다.

즉 누적합을 이용하면 알고리즘이 훨씬 빠르게 구할수있습니다.

 

소스코드 :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <bits/stdc++.h> using namespace std; #define ll long long int n; vector<ll> v,dp; void input() {     cin >> n;     v.resize(n+1);     dp = v;     for (int i = 1; i <= n; i++) {         cin >> v[i];         dp[i] = v[i] + dp[i - 1];     } } void solve() {     ll res = 0;     for (int i = 1; i < n; i++)          res += v[i] * (dp[n] - dp[i]);     cout << res << "\n"; } int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     cout.tie(0);     input();     solve();   }     Colored by Color Scripter

cs

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.