[BOJ] BOJ_11659 구간 합 구하기 4 (JAVA)

[문제 - 11659번: 구간 합 구하기 4 (JAVA)]

[접근 방법]

1. 2중 for 문을 이용하여서, arr[i] ~ arr[j] 까지 누적합을 구하는 방법

=> 시간 초과

 

2. 2차원 배열 DP[i][j] 를 이용하여 (i, j) 의 값을 저장하는 방법

=> 메모리 초과

 

3. [(1 ~ j) 누적합] - [(1 ~ i-1) 누적합] 을 구하는 방법

=> 성공

 

[JAVA 코드]

[시간 초과 - 2중 for 문으로 누적합 구하기]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_11659 {
  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());
    //주어진 숫자 개수 N
    int N = Integer.parseInt(st.nextToken());

    //구해야 하는 횟수 M
    int M = Integer.parseInt(st.nextToken());
    
    //숫자 부여 받기 (N개)
    List<Integer> arr = new ArrayList<>();
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
      arr.add(Integer.parseInt(st.nextToken()));
    }

    //구해야 하는 횟수 M
    for (int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      int start = Integer.parseInt(st.nextToken());
      int end = Integer.parseInt(st.nextToken());

      //요소 합 구하기
      int result = 0;
      for (int j = start; j <= end; j++) {
        result += arr.get(j - 1);
      }
      bw.write(result + "\n");
    }

    bw.flush();
    bw.close();
  }
}

 

[메모리 초과 - 2차원 배열로 값을 미리 계산]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_11659 {
  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());
    //주어진 숫자 개수 N
    int N = Integer.parseInt(st.nextToken());
    //구해야 하는 횟수 M
    int M = Integer.parseInt(st.nextToken());

    int[][] DP = new int[N+1][N+1];
    //DP 배열 초기화
    for (int i = 0; i < N+1; i++) {
      Arrays.fill(DP[i], -1);
    }
    
    
    
    //숫자 부여 받기 (N개)
    st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      DP[i][i] = Integer.parseInt(st.nextToken());
    }

    //i = (1 ~ N-1) , j = (2 ~ N)
    for (int i = 1; i < N; i++) {
      for (int j = i + 1; j <= N; j++) {
        DP[i][j] = DP[i][j-1] + DP[j][j];
      }
    }


    //구해야 하는 횟수 M
    for (int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      int start = Integer.parseInt(st.nextToken());
      int end = Integer.parseInt(st.nextToken());

      bw.write(DP[start][end] + "\n");
    }

    bw.flush();
    bw.close();
  }
}

 

[성공 - (1~end) - (1~start-1) ]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_11659 {
  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());
    //주어진 숫자 개수 N
    int N = Integer.parseInt(st.nextToken());
    //구해야 하는 횟수 M
    int M = Integer.parseInt(st.nextToken());

    int[] arr = new int[N+1];
    int[] sum = new int[N+1];
    Arrays.fill(sum, 0); //배열 초기화
    
    
    
    //숫자 부여 받기 (N개)
    st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
      sum[i] = arr[i];
    }

    //sum : 1 ~ i 까지 arr 값의 합
    for (int i = 2; i <= N; i++) {
      sum[i] = sum[i-1] + arr[i];
    }


    //구해야 하는 횟수 M
    for (int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      int start = Integer.parseInt(st.nextToken());
      int end = Integer.parseInt(st.nextToken());

      int result = sum[end] - sum[start - 1];
      bw.write(result + "\n");
    }

    bw.flush();
    bw.close();
  }
}

 

[Rewind]

 

1. 어려웠던 점

메모리 / 실행 시간 조건을 맞추는 것이 어려웠다.

다이나믹 프로그래밍을 통해 해결하려 했으나, 2차원 배열의 메모리 문제 때문에 실패 하였다.

2. 알게된 점

문제 해결에 대한 적절한 방법을 찾는 하나의 방법을 알게 되었다.

3. 개선 방안

문제 실행 조건에 대한 분석을 자세히 해야 한다.

1) 실행 시간

2) 메모리 한계