[백준] 1749 점수따먹기 - JAVA

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

1749번: 점수따먹기

 

 

알고리즘

• 누적합/ 부분합 + 완전탐색 
• 주어진 2차원 배열에서 각 지점까지의 누적합을 구한다.
• N,M 범위 내에서 시작 지점과 도착 지점의 모든 가능한 경우의 수를 탐색하여 각 부분 행렬의 합을 구한다. 

---

 

구현 과정

• sum[][] : 각 지점까지의 누적합 저장한 2차원 배열 
• findSum(sx, sy, ex, ey) : 시작 지점 (sx, sy) ~ 도착 지점 (ex, ey) 의 부분 구간 합 구하는 메소드

 

1. 입력받은 2차원 배열을 map[][] 에 저장한다. 첫 열/행의 합도 포함시키기 위해 배열의 위쪽/왼쪽을 0으로 채운다. 즉, 입력값 저장은 1번 인덱스 부터 저장.

 

2. 시작점을 배열의 가장 왼쪽 상단으로 하여, 모든 지점까지의 누적합을 sum[][] 에 저장한다. 

(i,j) : sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + map[i][j] ;

 

3. (1~N), (1~M) 내에서 가능한 모든 시작 지점, 도착 지점에 대해 완전 탐색한다. 

 

4. 모든 경우의 시작 지점 ~ 도착 지점에 대해 부분 구간합을 구한다. (findSum 메소드) 

(sx,sy)~(ex,ey) : sum[ex][ey] - sum[sx-1][ey] - sum[ex][sy-1] + sum[sx-1][sy-1];

 

 

💡 누적합, 부분합 모두 '공통으로 포함 되는 구간'을 고려하며 식을 구한다. 

• 누적합 : (지점 이전의 부분/지점의 값)모든 부분합을 더한 후, 공통으로 포함되어 두번 더한 구간 빼기 
• 부분합 : 도착 지점까지의 누적합에서 시작 지점 이전의 모든 부분합을 뺀 후, 공통으로 포함되어 두번 뺀 부분 더하기

 

---

소스 코드

import java.util.*;
import java.io.*;
	
public class Main {
	static int max=Integer.MIN_VALUE;
	static int[][] sum; 
	public static void main(String[] args) throws Exception {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st;
		
		st= new StringTokenizer(br.readLine(), " ");
		int N= Integer.parseInt(st.nextToken());
		int M= Integer.parseInt(st.nextToken()); 
		int map[][] = new int[N+1][M+1];
		sum = 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++) {
				map[i][j] = Integer.parseInt(st.nextToken()); 
			}
		}
		
		//누적합 구하기 		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=M; j++) {
				sum[i][j] = sum[i-1][j] + sum[i][j-1] + map[i][j] - sum[i-1][j-1]; 
			}
		}
		
		
		//시작점, 끝점을 모든 경우의 수 완전 탐색 
		for(int sx= 1; sx<=N; sx++) {
			for (int sy=1; sy<=M; sy++) {
				for(int ex= sx; ex<=N; ex++) {
					for(int ey=sy; ey<=M; ey++) {
						int result= findSum(sx, sy, ex, ey);
						max= Math.max(max, result); 
					}
				}
			}
		}
		
		System.out.println(max);
		
	}//end of main 
	
	//(sx, sy) ~ (ex, ey) 구간합 구하기 
	private static int findSum(int sx, int sy, int ex, int ey) {
		return sum[ex][ey] - sum[sx-1][ey]- sum[ex][sy-1]+ sum[sx-1][sy-1]; 
	}
}//end of class