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

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

난이도: 실버 1

사용언어: JAVA

 

풀이

이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 특정 구간의 합을 dp라는 배열에 따로 저장하여 문제를 해결했습니다.

 

만일 예시와 같이 다음과 같은 입력이 주어졌다고 가정하겠습니다.

 

우선 4x4 크기의 표를 배열에 집어넣고 구간합을 구해줍니다. 구간합은 다음과 같이 구할 수 있습니다.

 

dp [3][2]에는 회색으로 색칠된 6개 구간의 합을 저장하고, dp [2][4]에는 주황색으로 색칠된 8개의 합을 저장하는 식입니다.

 

그리고 구해야 하는 구간의 좌표가 주어지면 다음과 같은 연산을 수행해주면 됩니다.

dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

예시에서처럼 (2,2) (3,4)가 주어진다면,

 

연보라색 부분을 구하는 것이 목표이기 때문에, dp [3,4]에서 하늘색 부분인 dp [1,4]와 분홍색 부분인 dp [3,1]을 빼줍니다. 이렇게 되면 진한 보라색 부분이 두 번 빼진 것이기 때문에, dp [1,1]을 한 번 더해주면 올바른 식을 완성할 수 있습니다.

 

import java.io.*;
import java.util.StringTokenizer;
 
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));
        int N,M;
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        int i, j;
        int [][]arr = new int[N+1][N+1];
        int [][]dp = new int[N+1][N+1];
        for(i=1;i<=N;i++){ // 입력을 1,1부터 받기 때문에 편의를 위해 배열도 0이아닌 1부터 사용
            s = br.readLine();
            st = new StringTokenizer(s);
            for(j=1;j<=N;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for(i=1;i<=N;i++){
            for(j=1;j<=N;j++){ // 구간합을 위한 dp배열 채워넣기
               dp[i][j] = arr[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
            }
        }
        int x1,x2,y1,y2;
        for(i=0;i<M;i++){
            s = br.readLine();
            st = new StringTokenizer(s);
            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());
 
            bw.write(String.valueOf(dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]+ "\n"));
        }
        bw.flush();
    }
}