[백준/자바(JAVA)] 구간 합 구하기5 11660 Silver 1

💌문제

---

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

11660번: 구간 합 구하기 5

 

💌풀이

---

누적합을 이용해서 풀어야 하는 문제이다.

누적합 아이디어는 배열에 들어있는 값이 바뀌지 않는다는 점을 이용한다. 앞에서부터 차례대로 누적된 합을 구해서 저장해둔 배열을 이용해서 구간 합을 구할 수 있다.

누적합 개념을 이용하지 않으면 시간초과가 발생하게 된다.

누적합은 반복문을 돌면서 이전 원소 인덱스까지의 합과 현재 원소 인덱스의 값을 계속해서 더한다. 즉, arr[i]+=arr[i-1] 과정을 통해 더하면 된다.

누적합을 이용해서 구간합은 arr[0~b까지의 누적합]-arr[0~(a-1)까지의 누적합]=arr[b]-arr[a-1]로 표현할 수 있다.

더 자세한 건 다음 블로그에서 확인할 수 있다. 

https://nahwasa.com/entry/%EB%88%84%EC%A0%81-%ED%95%A9prefix-sum-2%EC%B0%A8%EC%9B%90-%EB%88%84%EC%A0%81%ED%95%A9prefix-sum-of-matrix-with-java

누적 합(prefix sum), 2차원 누적합(prefix sum of matrix) with java

 

그렇다면, 2차원 배열에서의 구간 합은 다음과 같은 방식으로 구현할 수 있다.

1. 각 행마다 누적합을 구한다.

2. 구간합을 구할 때도 마찬가지로 각 행마다 구간합을 구해서 더해준다.

3. 구한 구간합은 StringBuilder를 이용해서 저장하여 한꺼번에 출력한다.

 

💌자바 코드

---

package org.example.day3;

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

public class jun11660 {
    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());
        int[][] num=new int[n+1][n+1];
        StringBuilder sb=new StringBuilder();
        for(int i=1;i<=n;i++){
            StringTokenizer t=new StringTokenizer(br.readLine());
            for(int j=1;j<=n;j++){
                num[i][j]=Integer.parseInt(t.nextToken());
            }
        }

        int[][] answer=new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                answer[i][j]=answer[i][j-1]+num[i][j];
            }
        }

        for(int i=1;i<=m;i++){
                StringTokenizer tt=new StringTokenizer(br.readLine());
                int x1=Integer.parseInt(tt.nextToken());
                int y1=Integer.parseInt(tt.nextToken());
                int x2=Integer.parseInt(tt.nextToken());
                int y2=Integer.parseInt(tt.nextToken());
                if ((x1==x2)&&(y1==y2)){
                    sb.append((answer[x1][y1]-answer[x1][y1-1])+"\n");}
                else{
                    int temp=0;
                    for(int j=x1;j<=x2;j++){
                    temp+=(answer[j][y2]-answer[j][y1-1]);

                    }   sb.append(temp+"\n");
                }
        }
        System.out.println(sb.toString());

        //(x1,y1) 부터 (x2,y2)의 합 , i는 1부터시작, J는 0부터 시작

    }
}