[백준 알고리즘] 11660번 자바(Java) 구간 합 구하기

조건

문제

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이다.

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

 

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

 

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

 

풀이

• 표의 크기 N이 최대 1024이고 횟수가 최대 10만번이다
  • 절대 이중반복문으로 구간 합을 구하지 말자 → 누적합이용
• 이말은 이중반복분 쓰지말고 저 표의 값을 어딘가로 받아야한다
• 2단 배열을 하나만들어 위치가 (x,y)인 값의 누적합을 구한다
  • 누적합을 어떻게 구해야할지를 고민 NxN이 아닌 N개의 수면 arr[i] = arr[i-1] + Integer.parseInt(st.nextToken())하면됨lineTable[i] = lineTable[i-1] + Integer.parseInt(st.nextToken()); arr[i][j] = 그행만의 누적합(따로 생성)+전행의 j번째까지의 누적합여기서 사라질배열은 그냥 매 행마다 생기는 배열
  • 처음 생성시 lineTable[j+1] 하고 lineTable[0]설정
  • arr[4][2] 한마디로 4행의 2열을 구한다면 사라질배열[j-1]+arr[3][2]
  • 그행만의 누적합 lineTable
• 위처럼 누적합을 구하고 이후에 범위 값을 구할려면
  table[x2][y2] - table[x2][y1-1] -table[x1-1][y2] + table[x1-1][y1-1] 이식을 사용하면 된다
  글보다는 그림이 빠를거같아서 밑에 그림을 참고하면 좋다

(3,3)부터 (6,6)까지의 구간합 구하는 방식

        결국 구간합 = 누적합 - 노란부분 이므로 노란부분을 구해줘서 풀면 되는 식이다
        이 과정을 진행할려면 table의 누적합을 이용해야함

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//11660번 문제

public class p11660{
    public static void main(String[] args)throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb= new StringBuilder();
        StringTokenizer st= new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());   //표의 크기
        int m = Integer.parseInt(st.nextToken());   //구해야하는 횟수

        int [][]table = new int[n+1][n+1];
        int [][]value = new int[n+1][n+1];

        for(int i = 0; i<=n; i++)
        {
            table[0][i] = 0;
            value[0][i] = 0;
        }
        //첫 행에 누적값 대입
        StringTokenizer line1 = new StringTokenizer(br.readLine());
        for(int i = 1; i<=n; i++)
        {
            value[1][i] =Integer.parseInt(line1.nextToken());
            table[1][i] = table[1][i - 1] + value[1][i];
        }


        //표 각각 위치의 누적값 table 배열에 대입하기
        for (int i = 2; i <=n; i++)
        {
            int []lineTable = new int[n+1];
            lineTable[0] = 0;
            table[i][0] = 0;
            value[i][0] = 0;
            StringTokenizer line2 = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++)
            {
                value[i][j] =Integer.parseInt(line2.nextToken());
                lineTable[j] = lineTable[j-1] + value[i][j];
                table[i][j] = lineTable[j] + table[i-1][j];
            }
        }

        //텍스트 케이스 돌리기
        for (int i = 0; i < m; i++)
        {
            StringTokenizer line3 = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(line3.nextToken());
            int y1 = Integer.parseInt(line3.nextToken());
            int x2 = Integer.parseInt(line3.nextToken());
            int y2 = Integer.parseInt(line3.nextToken());
            if(x1 == x2&&y1==y2)
            {
                sb.append(value[x2][y2]+"\n");
            }
            else
            {
                int sum = table[x2][y2] - table[x2][y1-1] -table[x1-1][y2] + table[x1-1][y1-1];
                sb.append(sum+"\n");
            }
        }
        System.out.println(sb);
    }
}

 

- 개인적으로 11659번 구간 합 구하기 4를 먼저 풀고서 풀어보는걸 추천한다.

 

 

문제 출처

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5