15724번: 주지수
네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은
www.acmicpc.net
> 의식의 흐름
예전에 풀어봤던 사각형 내 합 구하는 문제랑 비슷하다.
(1 1 i j) 구역 내 사람 수를 dp에 담아두고 그때그때 원하는 구간의 사람 수 합을 다시 구하면 될 것 같다.
> 풀이 과정
1. 영토의 세로(N), 가로(M)의 크기를 입력 받는다.
2. 단위 구역 내 살고 있는 사람의 수를 배열(population)에 담는다.
3. (1 1 i j) 구역 내 살고 있는 사람의 수를 배열(dp)에 담는다.
dp = new int[N+1][M+1]; // dp[i][j] = (1 1 i j)구역 내 살고 있는 사람 수
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1] + population[i][j] - dp[i-1][j-1];
}
}
4. 진경대왕이 인구 수를 궁금해하는 직사각형 범위의 개수(K)를 입력 받는다.
5. 직사각형 범위(x1, y1, x2, y2)를 입력 받는다.
6. 직사각형 범위 내 사람의 수를 구한다.
dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]
7. 5번-6번 과정을 K번만큼 반복한다.
8. 정답을 출력한다.
> 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K, x1, x2, y1, y2;
public static int[][] population;
public static int[][] dp;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 세로
M = Integer.parseInt(st.nextToken()); // 가로
population = new int[N+1][M+1];
for(int i=1;i<=N;i++){
st = new StringTokenizer(br.readLine());
for(int j=1;j<=M;j++){
population[i][j] = Integer.parseInt(st.nextToken());
}
}
dp = new int[N+1][M+1]; // dp[i][j] = (1 1 i j)구역 내 살고 있는 사람 수
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1] + population[i][j] - dp[i-1][j-1];
}
}
K = Integer.parseInt(br.readLine());
while(K-->0){
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());
bw.write(Integer.toString(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1])+"\n");
}
bw.flush();
br.close();
bw.close();
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[JAVA] 백준 q9084 - 동전 (0) | 2023.10.25 |
---|---|
[JAVA] 백준 q9251 - LCS (0) | 2023.10.24 |
[JAVA] 백준 q1607 - 숨바꼭질 (2) | 2023.10.20 |
[JAVA] 백준 q15486 - 퇴사2 (0) | 2023.10.19 |
[JAVA] 백준 q11055 - 가장 큰 증가하는 부분 수열 (0) | 2023.10.18 |