BJ S1 11660 구간 합 구하기 5 - Java

[문제링크]

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

 

---

[문제]

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

---

[입력]

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

---

[출력]

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

---

[예제 입력 1]

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

---

[예제 출력 1]

27
6
64

 

---

[예제 입력 2]

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

---

[예제 출력 2]

1
2
3
4

 

[설명]

보통 문제에서 100,000까지의 범위가 있다면, O(N^2)으로는 시간초과가 나올것이다. 따라서 조금 더 깊게 생각해 봐야 한다. 범위의 합을 구하는 문제이기 때문에 누적합일거라 판단하였다.이 문제에서 주의할 점은 1) 0,0에서 시작하는게 아니라 1,1에서 시작하는 점 2) 범위 설정을 잘 하는것 이다.

 

총 4개의 범위로 나누었는데, 입력받는 좌표를 (r1,c1), (r2, c2)라고 했을 때,
1) r1 과 c1이 모두 1 보다 클 경우.2) r1이 1이고, c1이 1보다 클 경우.3) r1이 1보다 크고, c1이 1인 경우.4) r1과 c1이 모두 1인 경우.로 나누어 문제를 해결하였다.

 

1) sum 배열을 구하는 방법과 동일하게, 구하였다.answer = sum[r2 - 1][c2 - 1] - sum[r2 - 1][c1 - 2] - sum[r1 - 2][c2 - 1] + sum[r1 - 2][c1 - 2];2) 왼쪽을 뺄 필요가 없기 때문에 전체에서 위쪽만 빼면 된다.answer = sum[r2 - 1][c2 - 1] - sum[r2 - 1][c1 - 2];3) 위쪽을 뺄 필요가 없기 때문에 전체에서 왼쪽만 빼면 된다.answer = sum[r2 - 1][c2 - 1]- sum[r1 - 2][c2 - 1];4) 위쪽과 왼쪽을 뺄 필요가 없기 때문에 전체 범위만 고르면 된다.answer = sum[r2 - 1][c2 - 1];

 

이렇게 범위를 나누어 풀면 성공하게 된다.

 

 

 

백준 알고리즘 11660번 JAVA풀이

 

import java.util.*;

public class BJ11660 {
    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[][] sum = new int[N][N];

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                int a = sc.nextInt();
                arr[i][j] = a;
            }
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(i==0 && j==0) {
                    sum[i][j] = arr[i][j];
                }else if(i == 0 && j != 0){
                    sum[i][j]  = sum[i][j-1] + arr[i][j];
                }else if(i != 0 && j == 0){
                    sum[i][j] = sum[i-1][j] + arr[i][j];
                }else{
                    sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j];
                }
            }
        }

        // 합을 구해야하는 횟수
        for(int i=0;i<M;i++){
            int r1 = sc.nextInt();
            int c1 = sc.nextInt();
            int r2 = sc.nextInt();
            int c2 = sc.nextInt();
            int answer = 0;
            if(r1!=1 && c1!=1) {
                answer = sum[r2 - 1][c2 - 1] - sum[r2 - 1][c1 - 2] - sum[r1 - 2][c2 - 1] + sum[r1 - 2][c1 - 2];
            }else if(r1==1 && c1!=1){
                answer = sum[r2 - 1][c2 - 1] - sum[r2 - 1][c1 - 2];
            }else if(r1!=1 && c1==1){
                answer = sum[r2 - 1][c2 - 1]- sum[r1 - 2][c2 - 1];
            }else {
                answer = sum[r2 - 1][c2 - 1];
            }
            System.out.println(answer);
        }

    }
}

 

 

 

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.