[백준, 자바] 13900번 순서쌍의 곱의 합, 누적합

1. 문제

https://www.acmicpc.net/problem/13900

 

2. 코드

완전 탐색을 통해 2중 for문을 사용할 수 있겠지만, N이 100,000이므로 시간초과가 발생할 것이다.

따라서 누적해서 계산할 수 있는 규칙을 찾아서 해결하였다.

• N = 4, arr = [2, 3, 2, 4]
• (2, 3) + (2, 2) + (2, 4) + (3, 2) + (3, 4) + (2, 4)
  • 인덱스 2로 시작하는 총합 : 6 + 4 + 8 = 18
  • 인덱스 3으로 시작하는 총합 : 6 + 12 = 18
  • 인덱스 2로 시작하는 총합 : 8
  • 결론 : 18 + 18 + 8 = 44
• 그러나 다음과 같이 규칙을 찾을 수 있다.
  • (2, 3) + (2, 2) + (2, 4) -> 2 * (3 + 2+ 4) = 18
  • (3, 2) + (3, 4) -> 3 * (2 + 4) = 18
  • (2, 4) -> 8
  • 결론 : 18 + 18 + 8 = 44
• 따라서 다음과 같이 코드를 작성하면 된다.
  • 배열에 있는 모든 숫자의 합을 sum에 저장한다.
  • for문을 돌면서, sum에서 현재 인덱스의 값을 빼주고, 현재 인덱스의 값 * sum을 answer에 더하면 된다.
    • sum - numbers[i]를 통해 다음 인덱스 ~ 끝 인덱스까지의 합을 구할 수 있음
    • answer은 모든 숫자 쌍의 합

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

public class Main {

    static int N;
    static int[] numbers;
    static long answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        numbers = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::valueOf)
                .toArray();

        long sum = sum();
        for (int i = 0; i < N; i++) {
            sum -= numbers[i];
            answer += numbers[i] * sum;
        }

        System.out.println(answer);
    }

    static long sum() {
        long sum = 0;
        for (int i = 0; i < N; i++) {
            sum += numbers[i];
        }
        return sum;
    }
}