백준 - 11660 구간 합 구하기 5 [DP]

14719번: 빗물

 

1. 문제 요약

(2,2)와 (3,4)가 주어졌을 경우

N x N의 표가 주어지고 좌표가 주어지면, 그 구간의 합계를 구하는 문제이다.

 

2. 접근 방법

다이내믹 프로그래밍을 이용하여 각각의 구간별 합을 미리 구해놓는다. (DP 테이블)

예를 들어, DP 테이블의 (2,2)의 위치는

기존테이블의 (2,2) + DP(2,1) + DP(1,2) - DP(1,1)이다

즉, 원하는 위치의 수 + DP테이블의 위 + 좌 - 겹치는 구간이다

• DP테이블은 (N+1) x (N+1)로 생성하면 편리하다. (메모리를 더 잡아먹기 때문에 필수는 아님)

 

좌표가 주어지면 앞서 구해놓은 DP 테이블을 이용하여 계산한다.

(2, 2), (3, 4)을 구해야 할 경우 (3, 4) - (1, 4) - (3, 1) + (1, 1)이다.

(x1, y1), (x2, y2)가 주어질 경우

목표 = (x2, y2) - (x1 -1, y2) - (x2, y1 -1) + (x1 -1, y1 -1)로 나타낼 수 있다. 

 

3. 파이썬

from sys import stdin
input = stdin.readline

N, M = map(int, input().split())
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

# dp 테이블 세팅
for i in range(N):
    data = list(map(int, input().split()))
    for j in range(N):
        dp[i+1][j+1] = data.pop(0) + dp[i][j+1] + dp[i+1][j] - dp[i][j]

# 정답 계산 및 출력
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    answer = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
    print(answer)

 

4. 자바

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());

    // dp 테이블 세팅
    int[][] dp = new int[N + 1][N + 1];
    for (int i = 1; i < dp.length; i++) {
        st = new StringTokenizer(br.readLine());
        for (int j = 1; j < dp[i].length; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + Integer.parseInt(st.nextToken());
        }
    }

    // 정답 계산 및 입력
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    for (int i = 0; i < M; i++) {
        st = new StringTokenizer(br.readLine());
        int x1 = Integer.parseInt(st.nextToken());
        int y1 = Integer.parseInt(st.nextToken());
        int x2 = Integer.parseInt(st.nextToken());
        int y2 = Integer.parseInt(st.nextToken());

        int answer = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
        bw.write(answer + "\n");
    }

    // 출력
    bw.flush();
    bw.close();
}

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/11660.%E2%80%85%EA%B5%AC%EA%B0%84%E2%80%85%ED%95%A9%E2%80%85%EA%B5%AC%ED%95%98%EA%B8%B0%E2%80%855