[백준 23827] 수열 (Easy) [Java]

문제

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

 

---

풀이

주어진 수열에 대해 1 ≤ i < j ≤ N을 만족하는 모든 정수쌍 (i, j) 곱의 합을 구하는 문제다.

수가 너무 커질 수 있으니 1e9 + 7로 나눈 나머지를 출력해야 한다.

문제를 만족하는 정수쌍 곱의 합은 i와 i + 1 ~ j의 합의 곱과 같다.

최대 길이가 50만인 수열에 대해 누적합을 미리 구해

        // Solve
        final int MOD = (int) (1e9 + 7);
        long[] prefixSum = new long[N];
        prefixSum[0] = A[0];
        for (int i = 1; i < N; ++i) {
            prefixSum[i] = prefixSum[i - 1] + A[i];
        }

모든 i에 대한 A[i] * ( prefixSum[N] - prefixSum[i] )을 구하면 된다.

        long res = 0;
        for (int i = 0; i < N; ++i) {
            res = (res + A[i] * (prefixSum[N - 1] - prefixSum[i]) % MOD) % MOD;
        }

풀이시간

≤ 3m

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/23827.java

problem-solving/baekjoon-online-judge/easy/23827.java at main · rogi-rogi/problem-solving