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

🔗 문제

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

11660번: 구간 합 구하기 5

 

💻 풀이 및 코드

문제 유형 : 다이나믹 프로그래밍, 누적 합

 

2차원 배열에서 시작 지점과 끝 지점 사이의 값들의 합을 구하는 문제 

 

풀이

총 2가지 방법으로 풀었다. 처음에 푼 방법으로 1412ms 가 나왔는데 채점 현황을 보니 900ms 로 푼 사람이 있어서 다른 풀이 방식을 찾아봐서 다시 풀었다.

첫 번째 풀이 방법이 두 번째보다 더 쉽지만 시간이 더 오래 걸린다.

 

첫 번째 풀이 방법)

arr 은 문제 예시에서 주어진 배열이다. dp 에는 행별로 누적합을 저장한다. 

 

문제 예시를 살펴보자.

문제 예시에서 구해야할 값은 파란색으로 색칠한 구간의 합이다.

dp[2][4] 는 arr[2][1] ~ arr[2][4] 와 같고 dp[3][4] 는 arr[3][1] ~ arr[3][4]와 같다.

따라서 문제에 주어진 구간합의 값은 (dp [2][4] - dp [2][1]) + (dp [3][4] - dp [3][1]) 과 같다.

 

두 번째 방법)

먼저 dp[i][j] 를 구하는 방법을 살펴보자.

 

문제에서 주어진 구간의 합을 구하려면

 

과 같다. 

---

전체 코드

첫 번째 방법)

import java.io.*;
import java.util.*;

public class Main_bj_11660_구간합구하기5 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_11660.txt"));
		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[][] sum = 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++) {
				sum[i][j] = sum[i][j - 1] + Integer.parseInt(st.nextToken());
			}
		}

		StringBuilder sb = new StringBuilder();
		int x1, y1, x2, y2, total;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			x1 = Integer.parseInt(st.nextToken());
			y1 = Integer.parseInt(st.nextToken());
			x2 = Integer.parseInt(st.nextToken());
			y2 = Integer.parseInt(st.nextToken());
			
			total = 0;
			y1--;
			for(int j=x1; j<=x2; j++) {
				total = total + sum[j][y2] - sum[j][y1];
			}
			
			sb.append(total).append("\n");
		}
		
		System.out.println(sb.toString());
		br.close();
	}

}

 

두 번째 방법)

import java.io.*;
import java.util.*;

public class Main_bj_11660_구간합구하기5_sol2 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_11660.txt"));
		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[][] 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] + dp[i-1][j] - dp[i-1][j-1] + Integer.parseInt(st.nextToken());
			}
		}
		
		int sx, sy, ex, ey, total;
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			sx = Integer.parseInt(st.nextToken());
			sy = Integer.parseInt(st.nextToken());
			ex = Integer.parseInt(st.nextToken());
			ey = Integer.parseInt(st.nextToken());
			
			total = 0;
			total = dp[ex][ey] - dp[ex][sy-1] - dp[sx-1][ey] + dp[sx-1][sy-1];
			sb.append(total).append("\n");
		}
		System.out.println(sb.toString());
		br.close();
	}

}

 

채점 결과

---

Reference

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