13900 순서쌍의 곱의 합 ⬛

📋문제 정리

• 주어진 정수들의 다른 위치의 두 수를 뽑아 곱셉의 합을 구해라.
• 2,3,4가 주어지면 2,3 / 2,4 / 3,4 들의 곱의 합을 구하면 된다.

🎯풀이

• 언뜻보면 조합처럼 보이지만 중복된 수가 들어가기 때문에 될 수 없다.
• 결국 식을 생각해보면 x1,x2,x3일때 x1x2 + x1x3 +x2x3 이렇게 나온다.
• 이걸 묶어보면 x1(x2+x3)+ x2x3이 나온다.
• 결국 xa일때 a보다 큰 xn들의 합을 구하고 곱한 후 전부 더 하면 답이 나온다.
• 누적 합 배열을 만들어서 a일때 xn들의 합을 구하고 a를 곱하여 더해준다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static StringTokenizer st;
  static StringBuilder sb =  new StringBuilder();

  public static void main(String[] args) throws IOException {
    int n = Integer.parseInt(br.readLine());
    st = new StringTokenizer(br.readLine());
    int arr[] = new int[n]; //기본 배열
    long ps[] = new long[n+1]; //누적 합 배열
    long result =0;

    for(int i=0;i<n;i++){
      arr[i] =Integer.parseInt(st.nextToken());
      ps[i+1] = ps[i] + arr[i]; // 누적 합 배열 초기화
    }

    for(int i=0;i<n;i++){
      result += arr[i] *(ps[n]-ps[i+1]); // xa * (xn들의 합)
    }

    sb.append(result);
    System.out.println(sb);
    br.close();
  }
}