[Java] 문제 004(백준 11660번)

문제

---

구간 합 구하기 5(Baekjoon: 11660번)

 

 

풀이

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
  public static void main(String[] args) throws Exception {
      // n, m 입력받기
    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());

    // 주어진 2차원 배열 요소 입력받기
    int A[][] = 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++) {
        A[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    // 2차원  합 배열 구하기
    int D[][] = new int[N + 1][N + 1];
    for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= N; j++) {
        D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j];
      }
    }

    // 2차원 합 배열을 이용한 질의 답변하기
    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 result = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + D[x1 - 1][y1 - 1];
      System.out.println(result);
    }
  }
}

설명

---

개요

2차원 구간 합 배열 D[x][y]는 다음처럼 해석할 수 있다.
"주어진 2차원 배열의 (0, 0)부터 (x, y)까지의 사각형 영역 안에 있는 수의 합이다."

그럼 합 배열은 어떻게 채울까?
D[i][j]의 값을 채우려면, D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]임을 이용하면 된다.

또 질의 x1, y1, x2, y2에 대한 답도 아래처럼구간 합으로 구하면 된다.
D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]

합 배열 구하기

이는 D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]를 이용하면 된다.

예로 D[2][2]를 구한다고 치자.
그럼 D[2][2] = D[2][1] + D[1][2] - D[1][1] + A[2][2]이다.
이를 그림으로 이해해 보자.

 

D[2][2](파란색 물음표)를 구하려면 위 그림처럼 구하면 된다.

- D[1][1]을 하는 이유는 D[2][1] + D[1][2]에서 D[1][1]이 중북해서 더해졌기 때문이다.
이를 일반화하면 D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]에 도달한다.

질의 x1, y1, x2, y2에 대한 답

이는 D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]로 구하면 된다.

예로 (2, 2) ~ (3, 4)까지의 구간 합을 구한다 치자.
그럼 D[3][4] - D[1][4] - D[3][1] + D[1][1]이 된다.
이를 그림으로 이해하면 다음과 같다.

 

 

다시 1시간 제한 걸고 푼 후 틀린 풀이

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

public class Main
{
	public static void main(String[] args) throws IOException{
		//첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다.
		//  (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 
		//표에 채워져 있는 수가 1행부터 차례대로 주어진다
		//다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력
		//
		//표에 채워져 있는 수는 1,000보다 작거나 같은 자연수 => 10의 9제곱이면 다 합해도 int 범위 내겠네 -> 안전하게 long으로 하하는
		//
		//구간합: 합배열, s[1]=a[1], s[i]=s[i-1]+a[i] => 공식은 s[j]-s[i-1]
		//차이점은 2차원 배열이라는 거 
		
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		
		//이차원 배열에 입력받기, n곱하기 n개의 숫자를, 연산횟수는 10의 6제곱이고 1억번이 1초니까 백만번이면 노 상관
		int[][] a=new int[n+1][n+1];
		for(int i=1;i<=n;i++){
		    for(int j=1;j<=n;j++){
		        a[i][j]=sc.nextInt();
		    }
		}
		
		int[][] s=new int[n+1][n+1];
	    //y가 1일 때 s를 초기화 => 이건 맞음
	    for(int i=1;i<=n;i++){
	        s[i][1] = s[i-1][1] + a[i][1];
	    }
	    //x가 1일 때 => 이건 맞음
	    for(int i=1;i<=n;i++){
	        s[1][i] = s[1][i-1] + a[1][i];
	    }
	    //나머지 합 배열을 다 구해놓기 => 여기서 틀림
	    for(int x=2;x<=n;x++){
		    for(int y=2;y<=n;y++){
		        // x,y 좌표가 2, 2일 때만 테스트함 -> 3,3일 경우도 생각한 후 일반화 해야 하는데
	            s[x][y]= s[1][y]+s[x][1]-s[1][1]+a[x][y];

		    }
		}
		
		//x1, y1, x2, y2가 주어지니 이를 받고 출력해야 함
		int x1, y1, x2, y2 = 0;
		for(int i=1;i<=m;i++){
		    x1=sc.nextInt();
		    y1=sc.nextInt();
		    x2=sc.nextInt();
		    y2=sc.nextInt();
		    
		    //출력하기 -> 함수로 만들기
		    priAns(s,x1, y1, x2, y2);
		}
		
	}
	// 나머지 핵심 로직은 같고, s[1][1] 부분만 틀림 => s[x1-1][y1-1]이 맞는데
	public static void priAns(int[][] s, int x1, int y1, int x2, int y2){
	    //2,2 -> 3,4까지의 합은 
	    //1,1 -> 3,4까지 - 1,1-> 1,4 - 1,1->3,1 + 1,1
	    
	    //일반화하면 1,1->x2, y2 - 1,1->1,y2 - 1,1->x2,1 +1,1 

	    System.out.println(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[1][1]);
	}
}

 

일반화를 할 때 한 가지 입력값만 적용하고 끝내니, 다른 경우엔 해당 못하는 일반화 공식을 도출함

이러한 접근법은 틀린 건 아니고, 코드가 엉망이라도 되기만 하면 되는 게 아닌가.

scanner 대신 buuferedReader를 쓰니 마니는 구현 코어 로직을 완료한 후에 시간 남으면 신경 쓸 부차적인 잡코드라고 생각함.

핵심 로직을 짤 땐, 이렇게 경우 몇 가지 대입하면서 일반화 하는 접근법을 고칠 필요는 없음.

이를 더 숙련해야 한다고 생각함.

 

24.5.31) 다시 풀고 맞은 풀이

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

public class Main
{
	public static void main(String[] args) throws IOException{
// 		첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M . (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000)
// 		둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다
// 		음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력
		
// 		핵심 로직 
// 		    s[i][j]
// 		    어떻게 채워넣을까?
// 		        1행, 1열은 일단 근야 채워넣을 수 있으니 체워넣고 
// 		        ~~ + a[][]일 건데, 
// 		        s[2][2]=s[1][2]+s[2][1]-s[1][1]+ a[2][2]
// 		        s[3][4]=s[3][3]+s[2][4]-s[2][3] +a[3][4]
// 		        일반화하면, s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1] +a[i][j]
// 		    구간 합을 어떻게 구할까?
// 		        2,2 -> 3,4 
// 	                구간 합은, s[3][4]-s[3][1]-s[1][4]+s[1][1]
// 	            3,1->4,4 
// 	                s[4][4]-s[2][4]
//                 2,1->4,2 
//                     s[4][2]-s[1][2]
//                 2,3->4,4 
//                     s[4][4]-s[4][2]-s[1][4]+s[1][2]
//                 일반화하면 
//                     s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]
        
//         슈도코드
//             n,m을 받는다 
//             각 줄의 원소를 받으면서, 2차원 배열 a에 채워넣는다. -> n번 반복 
//             합 배열을 만든다 
//             x1,y1.x2,y2 받고 구간 합 공식을 통해 답을 출력한다. -> m번 반복 
            
        // 왜 틀렸지?
        //     1 1 4 4를 입력하니 64가 아니라 52가 나옴, 왜?
        //     일단 틀릴 확률 높은 부분이 구간 합 정답 출력하는 공식인데
        //     s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]잖아
        //     대입하면, s[4][4]-s[4][0]-s[0][4]+s[0][0]
        
        // n,m을 받는다 
        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());
        
        // 각 줄의 원소를 받으면서, 2차원 배열 a에 채워넣는다. -> n번 반복 
        int[][] a=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++){
                a[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        
        // 합 배열을 만든다 
        int[][] s=new int[n+1][n+1];
        // 1열만 만들기 
        for(int i=1;i<=n;i++){
            // s[i]=s[i-1]+a[i] 
            s[i][1]=s[i-1][1]+ a[i][1];
            
        }
        // 1행만 받음
        for(int j=1;j<=n;j++){
            s[1][j]=s[1][j-1]+a[1][j];

        }
	    
	    // 합 배열 전체 채우기 
	    for(int i=2;i<=n;i++){
	        for(int j=2;j<=n;j++){
                s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1] +a[i][j];
            }
	    }
	    
	    //debug  => 디버그 결과 틀린 부분은 구간 합 공식이 아니라 합 배열 만드는 과정일 거란 추측을 해봄
	   // System.out.println(s[4][4]-s[4][0]-s[0][4]+s[0][0]); //52
 	   // System.out.println(s[4][4]); //52
	   // System.out.println(s[4][0]); //0
	   // System.out.println(s[0][4]); //0
	   // System.out.println(s[0][0]); //0
	    
	    //x1,y1.x2,y2 받고 구간 합 공식을 통해 답을 출력한다. -> m번 반복 
	    for(int i=1;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());
	        
	        System.out.println( s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
	    }
	}
}

 

일단 처음에 푼 코드를 해보니 1 1 4 4의 값이 64가 아니라 52가 나옴

왜 그런지 디버그를 할 땐 위 코드처럼 틀릴 확률이 높은 부분의 변수부터 확인해 봄

일일이 프린터문 써서 확인해 본 결과 틀린 부분은 구간 합 공식 부분이 아니라, 합 배열 만드는 과정이라고 추측함

 

역시나 합 배열 만드는 부분에서 1행, 1열 부분만 만드는 코드가 있음

s[i][1]=s[i-1][1]+ a[i][1];

s[1][j]=s[1][j-1]+a[1][j];

 

위에 처럼 써야 하는데, 

s[i][1]= a[i][1]

이런 식으로 해 놔서 틀린 거였음

 

다시 풀어본 결과 대략 40분 정도 쓰고 맞은 것 같음

디버그 다 포함해서