[백준] no11659: 구간 합 구하기 4

문제

N개의 숫자를 나열 하여, 그 중 i번째 부터 j번째까지의 구간 합을 N개 구하기

 

문제 링크 : https://www.acmicpc.net/problem/11659

 

---

원리

각 순서까지의 합을 나열해놓고, j번째에서 i-1번째를 빼면 된다.

* 나열해놓고 for문으로 하나씩 구하면 시간초과된다.

---

풀이방법

예를들어, 

5 4 3 2 1 이 주어지고, 3번째부터 5번째까지 구해야 한다면,

5 9 12 14 15에서, 15-9=6이며, 이는 3+2+1=6과 같다.

---

나의 코드

1. 일반 이중반복문으로 구했을 경우 [ 시간초과 발생 ]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    StringTokenizer stN = new StringTokenizer(br.readLine(), " ");
    List<Integer> listN = new ArrayList<>();
    listN.add(0);
    for(int i = 0 ; i<N ; i++) listN.add(Integer.parseInt(stN.nextToken()));

    for(int i = 0 ; i<M ; i++) {
        StringTokenizer stM = new StringTokenizer(br.readLine(), " ");
        int head = Integer.parseInt(stM.nextToken());
        int tail = Integer.parseInt(stM.nextToken());
        int temp;
        if(head>tail) {
            temp = tail;
            tail = head;
            head = temp;
        }

        int sum = 0;
        for(int j = head ; j <= tail ; j++) sum += listN.get(j);
        bw.write(""+sum+"\n");
    }

    bw.close();
}

 

2. 구간합의 차이로 구하는 경우 [ 성공 ] 

public class no11659 {

    public static void main(String[] args) throws IOException {
        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());
        StringTokenizer stN = new StringTokenizer(br.readLine(), " ");
        List<Integer> list = new ArrayList<>(); // 구간합들을 받을 list
        list.add(0); // list의 0번째 인덱스를 미리 0으로 채워줌 (1부터 셀 것이기 때문에)
        for(int i = 1 ; i<=N ; i++) list.add(i, list.get(i-1) + Integer.parseInt(stN.nextToken())); // 구간 합을 순차적으로 넣어줌

        /**
         * M개의 입력에 따라 구간합들을 출력해주는 구간
          */
        while(M-->0) {
            StringTokenizer stM = new StringTokenizer(br.readLine(), " ");
            int head = Integer.parseInt(stM.nextToken());
            int tail = Integer.parseInt(stM.nextToken());
            int result = list.get(tail) - list.get(head-1); // head번째(i번째) 수를 포함시키기 위해선 i-1번째까지의 합을 빼야함
            System.out.println(result);
        }
    }
}

---

레퍼런스 코드

참고 링크 : https://yongku.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-11659%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-4-%EC%9E%90%EB%B0%94Java