[백준/13900] 순서쌍의 곱의 합 - JAVA

📌 문제

알고리즘 분류 : 누적합
난이도 : 실버4
출처 : 백준 - 순서쌍의 곱의 합

🦧 문제 풀이 접근

처음에 2중 for문을 이용해 sum을 구했을때 시간초과가 발생했다.
숫자를 입력받을때 마다 이전 값들의 합 X 새로 입력받을 값을 sum에 더해주는 방식의 누적합 알고리즘으로 해결했다.

ex) 1 2 3 4의 경우 0 + (1)2 + (1+2)3 + (1+2+3)*4 = 35

💻 code

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long sum=0;
        long temp=0;
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++) {
            int num = Integer.parseInt(st.nextToken());
            sum+=temp*num;
            temp+=num;
        }
        System.out.println(sum);
    }
}

🥇 결과

🎓 느낀점

간단하게 접근하기 보다는 수학적 원리를 잘 생각해서 알고리즘을 생각해보자.