[백준] 11660번 : 구간 합 구하기 5 – JAVA [자바]

 

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

11660번: 구간 합 구하기 5

 

---

• 문제

 

---

• 문제 풀이

백준 11660번 구간 합 구하기 5는 2차원 DP를 이용해서 푸는 다이나믹 프로그래밍 문제이다. DP 이론을 조금 더 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다.

 

https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

이 문제는 2가지 방식으로 풀었다. 첫 번째 방식은 조금 더 쉬울 수는 있으나 조금 더 느리고 두 번째 방식은 구현하고 생각해 내기가 조금 더 어려울 수는 있으나 확실히 더 빠르다.

 

---

문제 풀이 1

첫 번째 방식은 행별로 누적 합을 구하는 것이다. 문제에서 주어진 예시를 한번 보겠다.

2차원 배열 arr은 문제에서 주어진 입력으로 만든 2차원 배열이고 배열 dp는 행별로 누적 합을 구한 것이다.

(2, 2)부터 (3, 4)까지 누적합을 구한다고 하면 색칠되어 있는 부분의 합을 구해주면 된다. 

dp [2][4]와 dp [3][4]을 보겠다.

dp [2][4]는 arr [2][1]부터 arr [2][4]까지 더한 것이고 dp [3][4]는 arr [3][1]부터 arr [3][4]까지 더한 것이다. 따라서 (2,2)부터 (3,4)까지의 누적합은 (dp [2][4] - dp [2][1]) + (dp [3][4] - dp [3][1]) 과 같다.

 

---

문제 풀이 2

문제 풀이 1에서 본 방법은 행별로 누적합을 구하는 거였다면 두 번째 방법은 (1,1)부터 (i, j)까지 누적합을 구해서 푸는 것이다.

먼저 dp [i][j]를 어떻게 구하는지 살펴보겠다.

Ex) dp [3][4]

 

이제 문제에서 주어진 예제에서 (2,2)부터 (3,4)까지 누적합을 구해보겠다.

---

• 코드 1

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] 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][j-1] + Integer.parseInt(st.nextToken());
            }
        }
        for (int k = 1; k <= m; k++) {
            int sum = 0;
            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());
            for (int i = x1; i <= x2; i++) {
                sum = sum + (dp[i][y2] - dp[i][y1-1]);
            }
            sb.append(sum + "\n");
        }
        System.out.print(sb);
    }
}

 

---

• 코드 2

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n+1][n+1];
        int[][] 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++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j];
            }
        }
        for (int k = 1; k <= m; k++) {
            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 ans = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];
            sb.append(ans + "\n");
        }
        System.out.print(sb);
    }
}

 

---

• 후기

이 문제를 처음 접했을 때는 DP (다이나믹 프로그래밍)를 공부한 지 얼마 안 되었을 때였다. 그래서 이 문제를 풀 때 DP적인 사고를 못 해서 시간 초과가 나고 결국에는 못 풀었었는데 다른 DP 문제들을 풀고 이 문제로 돌아왔을 때 풀렸다. 진짜 알고리즘은 많이 하는 게 되게 중요한 거 같다.