문제 링크
https://www.acmicpc.net/problem/11660
🕒 Java 풀이시간: 30분
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int[][] arr=new int[n][n];
int[][] dp=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
arr[i][j]=sc.nextInt();
dp[i][j]=arr[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int left=0;
if(j>0)
left=dp[i][j-1];
int up=0;
if(i>0)
up=dp[i-1][j];
int left_up=0;
if(j>0&&i>0)
left_up=dp[i-1][j-1];
dp[i][j]+=left+up-left_up;
}
}
StringBuilder sb=new StringBuilder();
for(int i=0;i<m;i++){
int x1=sc.nextInt()-1;
int y1=sc.nextInt()-1;
int x2=sc.nextInt()-1;
int y2=sc.nextInt()-1;
int x1y2=0;
if(x1-1>=0)
x1y2=dp[x1-1][y2];
int x2y1=0;
if(y1-1>=0)
x2y1=dp[x2][y1-1];
int x1y1=0;
if(x1-1>=0&&y1-1>=0)
x1y1=dp[x1-1][y1-1];
sb.append(dp[x2][y2]-x1y2-x2y1+x1y1);
sb.append('\n');
}
System.out.println(sb.toString());
}
}2차원 배열의 누적합으로 영역 구하기 📊✨
2차원 배열에서 누적합을 사용하여 풀이하는 문제이다. 왼쪽에서 오는 경우는 누적되고, 위에서 오는 경우 또한 단순 누적이 된다. 이 때, 왼쪽과 위쪽에 모두 칸이 존재하는 경우, 누적합에서 대각선에 있는 칸, 즉 중복되는 칸을 빼주어야 제대로 된 누적이 된다. 그 이유는 누적합을 쌓으면서 중복되는 구간이기 때문이다.
이렇게 누적합을 구했으면 입력이 주어지는대로 답을 구해내야 하는데 이 때도 구간에서의 누적합을 통해 중복된 부분을 제거해주면 된다. x2,y2부터 x1,y1까지의 영역을 구한다면 우리가 빼내야 되는 부분은 그림을 그려본다면 x1-1,y2인 사각형과 x2,y1-1인 사각형을 빼내야 한다는 것을 알 수 있다. 이때 중복되는 부분이 x1-1,y1-1이 이루고 있는 사각형이므로 이를 다시 더해주면 된다.
이렇게 Java로 백준의 "구간 합 구하기 5" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
