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

0. 문제

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

11660번: 구간 합 구하기 5

 

1. 문제분석

- 그리드 상의 수를 누적해 구하는 문제로, 좌상단에서부터 누적된 수를 토대로 그리드 상 현재 위치의 누적된 값을 구해야한다는 점에서 DynamicProgramming을 사용해야 하는 전형적인 문제이다.

 

2. 주의할 점

- 비교적 쉬운 문제이기는 하지만, dp[i][j] 값에 대한 정의를 분명히 하고 부분합을 구하기 위한 i, j의 위치를 차분하게 한번 생각해보아야 한다.

- dp[i][j] : 그리드 상에서 [0][0]부터 [i][j]까지의 직사각형 안에 들어있는 모든 수를 더한 값

 

3. 소스코드(Java)

// boj 11660 구간합구하기5
// dp

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

public class boj_11660 {
    static int N, M;
    static int x1,y1,x2,y2;
    static int[][] dp;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = stoi(st.nextToken());
        M = stoi(st.nextToken());
        dp = new int[N+1][N+1];
        for (int i = 1; i <= N; ++i) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; ++j)
                dp[i][j] = dp[i-1][j] + dp[i][j-1] + stoi(st.nextToken()) - dp[i-1][j-1];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; ++i) {
            st = new StringTokenizer(br.readLine());
            x1 = stoi(st.nextToken()); y1 = stoi(st.nextToken());
            x2 = stoi(st.nextToken()); y2 = stoi(st.nextToken());
            sb.append(dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]).append('\n');
        }
        System.out.print(sb);
    }

    static int stoi(String s) {return Integer.parseInt(s);};
}

4. 여담

- 프로그램 수행 시간을 줄이기 위해서는 출력 시간을 최소화하는 것이 최고인 듯 하다. 이를 위해서는 StringBuilder를 사용하는 것이 좋다!