포스트

구간 합 구하기 4(11659)

게시 업데이트
By Kim Jung Wook 3 분읽는 시간

구간 합 구하기 4(11659)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

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

public class Main {
  
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    
    st = new StringTokenizer(br.readLine());
    
    int[] sumV = new int[n+1];
    
    int v;
    int sum = 0;
    for(int i = 1; i <= n; i++) {
      v = Integer.parseInt(st.nextToken());
      sum += v;
      sumV[i] = sum;
    }
    
    for(int i = 0; i < m ; i++) {
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      
      sb.append(sumV[b] - sumV[a-1]).append("\n");
    }
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
}

풀이과정

  1. 처음에는 문제에서 요구한 그대로 풀었다.
  2. 값을 받아서 배열에 할당하고, 시작과 종료 인덱스를 받아서 합을 구하는 코드를 구현하였다.
  3. 시간초과가 나왔다.
  4. 합을 구할 때 for문을 쓰다보니 (총 for문을 3번 쓰는형태) 시간초과가 발생한 듯 하였다.
  5. 그래서 메모라이징 기법을 사용하기로 하였다.
  6. 입력값을 받을 때 입력값이 아니라 해당 인덱스까지의 합을 넣었다.
  7. 시작과 종료 인덱스를 받았고, 종료 인덱스의 값은 1부터 종료 인덱스까지의 합이므로, 시작 인덱스의 전 인덱스의 합을 빼면
  8. 시작과 종료 인덱스 사이의 합이 되었다.
  9. 예) 5 4 3 2 1 입력
  10. sumV[1] = 5, sumV[2] = 5+4 = 9 , sumV[3] = 5+4+3 = 12, sumV[4] = 5+4+3+2 = 14, sumV[5] = 5+4+3+2+1 = 15
  11. 1에서 3까지의 합, sumV[3] - sumV[0](sumV[1-1]) : 5+4+3 - (0)
  12. 2에서 4까지의 합, sumV[4] - sumV[1](sumV[2-1]) : 5+4+3+2 - (5)
  13. 4에서 5까지의 합, sumV[5] - sumV[3](sumV[4-1]) : 5+4+3+2+1 - (5+4+3)
1
2
3

- 성공
- 메모리 : 56716 KB
- 시간 : 552 ms

보안점

  1. 문제를 접근할 때 직관적으로 푸는 것과 연산을 통해 응답시간을 단축시키는 것에 대해 실무 코드에서 적용을 어떻게 해야할지 상황에 따라 고민해봐야겠다.
알고리즘, 문제
알고리즘문제