[백준] 11660 - 구간 합 구하기 5 (JAVA)

1. 소요시간 : 30분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 1
4. 문제 유형 : 다이나믹 프로그래밍, 누적 합
5. 다른 사람의 풀이를 참고 했는가 ? : O
6. 문제 링크 : https://www.acmicpc.net/problem/2573
7. 푼 날짜 : 2023.05.16

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍 , 누적합

2. 사고과정

점화식이 떠오르지 않아서 풀이를 보며 공부했다.

dp[i][j]를 구하는 점화식은
dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+arr[i][j] 이다.

그리고 주어진 x1, y1, x2, y2 좌표에서
해당 범위 내의 누적합을 구하는 공식은
num = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] 이다.

이 점화식을 풀이를 1번 보고 이해한 후
이해한 것을 바탕으로 풀이를 보지 않고 그림 그려가며 범위를 구하며 코딩했다.

3. 풀이과정

1. 점화식을 세우고 해당 1,1에서부터 dp[j][j] 까지의 누적합을 구한다.
2. M번만큼 , 해당 범위 내의 누적합을 구하는 공식을 통해서 누적합을 계산한다.

4. 소스코드

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

public class Main {

	static int arr[][];
	static int dp[][];
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		arr=new int[N+1][N+1];
		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<dp.length;i++) {
			for(int j=1;j<dp.length;j++) {
				dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+arr[i][j];
			}
		}


		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 num = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];

			sb.append(num).append('\n');

		}

		System.out.println(sb);


	}


}

5. 결과

6. 회고

dp 는 내겐 너무 어렵다.
dp 까지만 잘해지고 싶다..

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212