[Eric's 백준] 13900번 - 순서쌍의 곱의합 - Java

안녕하세요! Eric 입니다!

오늘 풀어볼 문제는 백준 13900번 순서쌍의 곱의합 입니다!

우선 제가 처음에 시간 초과로 틀렸던 방법의 코드를 보고 

왜 시간초과가 났는지 알아보고

맞는 방법이 무엇인가 알아보도록 하죠!

시간초과 코드 (정답 아님)

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

public class N13900 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int sum = 0;

        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                sum += arr[i] * arr[j];
            }
        }
        System.out.println(sum);

        br.close();
    }
}

제가 처음 으로 작성했던 코드는

시간 초과 가 났었는데요,

그 이유는 이렇게 풀면 모든 경우의 수를 하나하나 브루트포스 방법으로

sum값에 더해주므로 계산할때마다 sum을 불러오고 더하기를 반복하므로

시간 초과가 날 수 있습니다.

 

해결법

그래서 시간 초과를 해결하기 위해서는

'누적합' 개념을 사용해야하는데용!

그 방법은

문제에 주어졌던 예제로 설명을하면,

그림으로 이해하기

그림으로 보시면 쉽게 이해 하실 수 있습니다!

 

그러면 이렇게 구현한 정답 코드는

 

정답 코드

저는 상단 그림의 빨간 부분을 long[]sum 으로 구현하였고,

input 값을 받을때마다 해당 값을 sum 배열에 누적하였습니다.

그리고 누적된 값을 answer 이라는 변수로 계산 후 출력하였습니다.