[랜덤 마라톤] 리그전 오브 레전드(23327)

1. 문제 풀이 아이디어

• 아래의 식을 참고하여 누적합을 활용하면 문제를 해결할 수 있다.

1 2 5*1
1 3 5*1 + (5+1)*2
1 4 5*1 + (5+1)*2 + (5+1+2)*3
1 5 5*1 + (5+1)*2 + (5+1+2)*3 + (5+1+2+3)*2
2 4 (5+1)*2 + (5+1+2)*3 - 5*(2+3)
4 5 (5+1+2+3)*2 - (5+1+2)*2
3 5 (5+1+2)*3 + (5+1+2+3)*2 - (5+1)*(3+2)

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());
        int q = Integer.parseInt(stringTokenizer.nextToken());
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int[] a = new int[n + 1];
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(stringTokenizer.nextToken());
            sum[i] = sum[i - 1] + a[i];
        }
        long[] mul = new long[n + 1];
        for (int i = 2; i <= n; i++) {
            mul[i] = mul[i - 1] + a[i] * sum[i - 1];
        }
        for (int i = 0; i < q; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int l = Integer.parseInt(stringTokenizer.nextToken());
            int r = Integer.parseInt(stringTokenizer.nextToken());
            stringBuilder.append(mul[r] - mul[l] - (sum[l - 1] * (sum[r] - sum[l]))).append('\n');
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

3. 정리

• 입력값을 처리하며 원래 배열과 누적합 배열을 생성한다.

• 2부터 n까지 순회하며 각 인덱스의 곱한 값을 mul 배열에 저장한다.

• 각 입력(l과 r)마다 결과값을 계산하여 출력한다.