[BOJ] 11660 구간 합 구하기 - JAVA

1. 문제

11660번: 구간 합 구하기 5

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

---

2. 풀이

board[i][j]는 board[i][j-1](왼쪽)과 board[i-1][j](위쪽)에 원래의 값을 더하면 된다. 하지만 왼쪽과 위쪽은 board[i-1][j-1]만큼의 중복된 부분이 있으므로 그만큼을 빼야한다.

board를 이용해서 입력받은 구간합을 구하려면 위와 비슷한 논리로 board[x2][y1-1](왼쪽끝)와 board[x1-1][y2](위쪽끝)을 빼준 뒤 대각선 board[x1-1][y1-1]을 뺀다.

 

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

public class BOJ_11660_구간합구하기5 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());

      int[][] board = new int[N + 1][N + 1];
      for (int i = 1; i <= N; i++) {
         st = new StringTokenizer(in.readLine());
         for (int j = 1; j <= N; j++) {
            //가로, 세로는 더하고 대각선은 빼기(중복)
            board[i][j] = board[i - 1][j] + board[i][j - 1] - board[i-1][j-1] + Integer.parseInt(st.nextToken());
         }
      }


      StringBuilder sb = new StringBuilder();
      int x1, y1, x2, y2, sum;
      for (int i = 0; i < M; i++) {
         st = new StringTokenizer(in.readLine());
         x1 = Integer.parseInt(st.nextToken());
         y1 = Integer.parseInt(st.nextToken());
         x2 = Integer.parseInt(st.nextToken());
         y2 = Integer.parseInt(st.nextToken());

         //가로 세로 빼고 대각선은 더하기(중복)
         sum = board[x2][y2] + board[x1-1][y1-1] - board[x2][y1-1] - board[x1-1][y2];

         sb.append(sum).append("\n");
      }

      System.out.print(sb);
   }
}

---

3. 결과

처음에 가로로만 합했다가 위+왼쪽-대각선 방식을 알게되어 코드를 변경했더니 시간이 단축되었다.