백준 11660번 자바 ☆

문제

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

11660번: 구간 합 구하기 5

import java.util.Scanner;

public class Main11660_1 {

	static int N,M;
	static int[][] map;
	static int[][] section;
	
	public static void sectionSum(int[] section) {
		int sum = 0;
		for (int i=section[0]; i<=section[2]; i++) {
			for (int j=section[1]; j<=section[3]; j++) {
				sum += map[i-1][j-1];
			}
		}
		System.out.println(sum);
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N][N];
		section = new int[M][4];
		
		for(int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		for(int i=0; i<M; i++) {
			for (int j=0; j<4; j++) {
				section[i][j] = sc.nextInt();
			}
		}
		
		for (int i=0; i<M; i++) {
			sectionSum(section[i]);
		}	
	}
}

import java.util.Scanner;

public class Main11660 {

	static int N,M;
	static int[][] map;
	static int[][] section;
	static int[][] allSum;
	
	public static void sectionSum(int[] section) {
		
		int sum = 0;
		if (section[0] == section[2] && section[1] == section[3]) {
			sum = map[section[0]-1][section[1]-1];
		} else {
			sum = allSum[section[2]-1][section[3]-1] - allSum[section[0]-1][section[1]-1];
		}
		
		System.out.println(sum);
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N][N];
		section = new int[M][4];
		allSum = new int[N][N];
		
		for(int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		for(int i=0; i<M; i++) {
			for (int j=0; j<4; j++) {
				section[i][j] = sc.nextInt();
			}
		}

		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if (j==0 && i==0) {
					allSum[i][j] = map[i][j];
				} else if (j==0 && i>0) {
					allSum[i][j] = allSum[i-1][N-1] + map[i][j]; 
				} else {
					allSum[i][j] = allSum[i][j-1] + map[i][j];	
				}
			}
		}
		
		for(int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				System.out.print(allSum[i][j] + " ");
			}
			System.out.println();
		}
		
		for(int i=0; i<M; i++) {
			sectionSum(section[i]);
		}
	}
}

1. 저번 dp 문제도 그렇고 dp문제는 항상 어렵다. 답을 봐도 사실 쉽게 이해가 가지 않는다. 많은 반복이 필요할듯 하다.

 

2. 일단 위 두개의 코드는 삽질하는 과정에서 나온코드이다. 첫번째는 시간복잡도를 고려안하고 매번 연산을 통해서 해결하는 방법이다. 최대 N*N*M의 연산을 진행하게 되기에 무조건 시간초과가 난다. (N최대값 : 1024, M최대값 : 10만)

 

3. 두번째 코드는 시간초과를 확인하고 dp를 통해 해결하고, 구간합이라는 개념을 적용해 푸는 방법을 해당문제에 적용 시켜본것이다. 무난하게 맞출거라 생각했지만 사실 생각이 잘못됐었다.

위 그림처럼 각 배열을 행열 순으로 전부 더했다. 그 결과 답이 계속 도출되지 않았고 결국 다른 블로그의 글들을 참고하여 진행했다.

 

4. 사실 위 방법이 막히고나서 전체를 구하지말고 행마다 구간합을 구해서 풀면 가능할까라고 생각을 했다. 다만 이 생각을 할 때 이미 몇시간을 문제를 풀던 중이라 더 시간을 끌고 싶지않았다. 다른 글들을 찾아보니 충분히 가능한 방법이긴 했다. 다만 속도면에서 다른 방식이 더 빠르기에 해당 방법은 비추천이다.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main11660_2{
    
	static int N;
	static int M;
	static int[][] map;
	static int[][] dpMap;
	static int[][] section;
	static List<Integer> sumList = new ArrayList<Integer>();
	
	public static void main(String[] args) {
        
		Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N+1][N+1];
        dpMap = new int[N+1][N+1];
        
        for (int i=1; i<=N; i++) {
        	for (int j=1; j<=N; j++) {
        		map[i][j] = sc.nextInt();
        	}
        }
        
        for (int i=1; i<=N; i++) {
        	for (int j=1; j<=N; j++) {
        		dpMap[i][j] = dpMap[i-1][j] + dpMap[i][j-1] - dpMap[i-1][j-1] + map[i][j]; 
        	}
        }
        
        for (int i=1; i<=M; i++) {
        	int x1 = sc.nextInt();
        	int y1 = sc.nextInt();
        	int x2 = sc.nextInt();
        	int y2 = sc.nextInt();
        	
        	int sum = dpMap[x2][y2] - dpMap[x2][y1-1] - dpMap[x1-1][y2] + dpMap[x1-1][y1-1];
        	sumList.add(sum);
        }
        
        for (int i:sumList) {
        	System.out.println(i);
        }
    }
}

5. 위의 코드가 정답인 코드다.

먼저 dpMap에 구간합을 구해준다. 

dpMap[i][j] = dpMap[i-1][j] + dpMap[i][j-1] - dpMap[i-1][j-1] + map[i][j];

여기서 dpMap[i][j]는 1행 1열 ~ i행 j열까지의 합을 나타낸 것이고 우항은 답을 구하기 위한 식이다.

 

dpMap에 구간합을 모두 저장했다면 조건에 맞는 구간합을 구해야한다. 예시로는 3행1열부터 4행3열까지의 구간합을 구하는것으로 표현했다. 배열을 애초에 N+1의 크기로 설정했기에 행이나 열에 0이 들어가면 값은 0이다. 

 

6. 그림을 그리며 공부를 하다보니 결국 2차원 배열도 1차원 배열 구간합 구하는 공식의 연장선이라는 생각이든다. 똑같이 하되 행과 열모두를 적용하고 중복되는 부분을 빼거나 더해주는 식으로 해결하는것이다. 완벽하게 이해하려면 시간이 걸리겠지만 반복해서 숙달하도록하자.

 

* 참고 블로그 : https://propercoding.tistory.com/29

[백준] 11660번 : 구간 합 구하기 5 – JAVA [자바]