과유불급 (누적합)

import java.io.*;
import java.lang.*;
import java.util.*;


public class Main {
    public static final Scanner scanner = new Scanner(System.in);
    /**
     *
     * @param n   카드의 수
     * @param m   앨범을 구매한 팬의 수
     * @param cards   각 카드에 적힌 숫자의 리스트 (cards[1] ~ card[n])
     * @param ranges  각 팬이 선택한 범위의 리스트 (ranges[0] ~ ranges[m-1])
     * @return        총 점수의 합이 가장 큰 범위 객체
     */
    public static Range getBestRange(int n, int m, int[] cards, Range[] ranges) {
        Range answer = ranges[0];

        long [] rangeSum = new long[n + 1];
        for(int i = 1; i < n + 1; i ++ ){
            rangeSum[i] = rangeSum[i - 1] + cards[i];
        }

        for(Range range : ranges){
            range.totalPoint =  rangeSum[range.right] - rangeSum[range.left -1];
            if(answer.totalPoint < range.totalPoint){
                answer = range;
            }
        }

        return answer;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] cards = new int[n+1];
        Range[] ranges = new Range[m];

        // 각 카드의 정보를 입력받는다.
        st = new StringTokenizer(br.readLine());
        for(int i = 1 ; i <= n ; i ++)
        {
            cards[i] = Integer.parseInt(st.nextToken());
        }

        // 팬들의 정보를 입력받는다.
        for(int i = 0 ; i < m; i ++)
        {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            ranges[i] = new Range(i + 1, l, r);
        }

        //범위의 합이 가장 큰 범위를 계산한다.
        Range answer = getBestRange(n, m, cards, ranges);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(answer.index + " " + answer.totalPoint);
        bw.flush();
    }

}

class Range{
    int index;
    int left;
    int right;
    long totalPoint;
    Range(int index, int left, int right)
    {
        this.index = index;
        this.left = left;
        this.right = right;
        this.totalPoint = 0;
    }
}

풀이방법

1. 각 카드의 정보를 입력받을때 n + 1의 범위를 지정해두는게 포인트이다.

2. 누적합을 구해 이 후에 점수 계산을 O(1)의 시간으로 구할 수 있다.

3. 점수가 가장 큰 사람을 구해서 리턴한다.

 

해맸던 점

1. 처음에는 시간 복잡도가 N^2인 풀이를 하여 시간 초과로 계속 실패했었다.

2. 결국은 점수를 구하는데 있어서 2중 for문이 발생하는게 문제였는데, 결국은 누적합이라는 개념을 알게 되어 그 방법으로 코드를 작성하게 되었다.