문제
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 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int N, *arr=NULL;
long long int mul=0, *sum=NULL;
scanf("%d", &N);
arr=(int *)malloc(N*sizeof(int));
sum=(long long int *)calloc(N,sizeof(long long int));
for(int i=0;i<N;i++)
{
scanf("%d", &arr[i]);
mul+=i>0?arr[i]*sum[i-1]:0;
sum[i]=i>0?sum[i-1]+arr[i]:arr[i];
}
printf("%lld\n", mul);
free(arr);
free(sum);
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 1356번: 유진수 (0) | 2020.10.28 |
---|---|
<백준 알고리즘> 15667번: 2018 연세대학교 프로그래밍 경진대회 (0) | 2020.10.28 |
<백준 알고리즘> 10179번: 쿠폰 (0) | 2020.10.27 |
<백준 알고리즘> 17256번: 달달함이 넘쳐흘러 (0) | 2020.10.27 |
<백준 알고리즘> 6591번: 이항 쇼다운 (0) | 2020.10.27 |