[자바] 백준 23827 - 수열 (Easy) (java)

 문제 : boj23827

---

 

필요 알고리즘 개념

•  누적 합 (prefix sum)
  • 누적 합 개념을 알고 있으면 더 편하게 풀 수 있다.
• 기본적인 수학
  
  • 수식을 편한 방식으로 짤 수 있도록 바꿀 수 있어야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  N=4에 대해 A1, A2, A3, A4를 생각해보자. i=1에 대해, A1*A2+A1*A3+A1*A4 = A1(A2+A3+A4) 이다. 마찬가지로 i=2에 대해, A2(A3+A4)이다. 그럼 구하려고 하는 답은 다음과 같이 나타낼 수 있다.

  그럼 우측 시그마 부분만 prefix sum으로 계산해둔다면 전체를 O(N)으로 처리할 수 있게 된다. 이 때 prefix sum을 거꾸로 진행하면(prefixSum[n] += prefixSum[n+1]) 위 수식의 우측 시그마를 바로바로 구해줄 수 있다.

 

  MOD값의 경우엔 이하의 두 수식에 의해 매번 나머지를 구해도 결과를 구할 때 문제되는 부분은 없다.

 

---

 

코드 : github

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

public class Main {
    private static final long MOD = 1000000007;
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] arr = new long[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) arr[i] = Long.parseLong(st.nextToken());
        long[] prefixSum = new long[n+2];
        for (int i = n; i >= 1; i--) {
            prefixSum[i] += prefixSum[i+1] + arr[i];
        }
        long sum = 0l;
        for (int i = 1; i <= n; i++) {
            sum += arr[i] * prefixSum[i+1];
            sum %= MOD;
        }
        System.out.println(sum);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}