[Java] 2차원 배열의 합 [2167번]

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

• 예제 입력1

2 3
1 2 4
8 16 32
3
1 1 2 3
1 2 1 2
1 3 2 3

• 예제 출력1

63
2
36

---

• 문제 접근
  • 첫째줄에는 2차원 배열의 크기가 주어짐 (N행 M열)
  • 둘째줄에는 2차원 배열의 값이 주어짐
  • 셋째줄에는 합을 구할 케이스가 주어짐
  • 넷째줄부터 누적 합을 할 좌표 가 주어짐[i , j] ~ [x, y]
  • 배열의 합이 2$^3$$^1$-1이하 이므로 int로 표현 가능
• 문제 해결
  • start X ~ end X, startY ~ endY 이중 반복문

• 슈도 코드

N(행 저장), M(열 저장)
A[N+1][M+1] 배열 선언
for(N번 반복){
	for(M번 반복){
		A 배열 초기화
	}
}
K(케이스 개수 저장)
for(K번 반복){
	startX, startY, endX, endY (입력 저장)
	sum (누적합)
	for(i = startX ~ endX)
		for(j = startY ~ endY)
			sum += A[i][j]
	sum 출력
}

• 코딩하기

public static void main(String[] args) throws Exception{
    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[][] A = 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++){
            A[i][j] = Integer.parseInt(st.nextToken());
        }
    }
    int K = Integer.parseInt(br.readLine());
    for(int k = 0; k < K; k++){
        st = new StringTokenizer(br.readLine());
        int startX = Integer.parseInt(st.nextToken()), startY = Integer.parseInt(st.nextToken());
        int endX = Integer.parseInt(st.nextToken()), endY = Integer.parseInt(st.nextToken());
        int sum = 0;
        for(int i = startX; i <= endX; i++){
            for(int j = startY; j <= endY; j++){
                sum += A[i][j];
            }
        }
        System.out.println(sum);
    }
}