백준 1749번 : 점수따먹기

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

1749번: 점수따먹기

 

 

 

 

 

문제

• 일단 N*M 행렬을 그린 다음, 각 칸에 -10,000 이상 10,000 이하의 정수를 하나씩 쓴다.
• 그런 다음 그 행렬의 부분행렬을 그려 그 안에 적힌 정수의 합을 구하는 게임이다.
• 정수의 합이 최대가 되는 부분행렬을 구해야 한다.

 

 

 

 

 

풀이

처음에는 이전에 풀었던 '부분행렬에서 부분합 구하는 문제'의 접근법과 유사하게 풀었다.

 

백준 11660번 구간 합 구하기5 : https://www.acmicpc.net/problem/11660

(풀이) 백준 11660번 구간 합 구하기5 : https://programmingiraffe.tistory.com/160

 

 

 

[방법1] O(N^4) 풀이 => 1000ms대

 

1. dp[i][j]로 (1, 1)~(i, j)의 누적합 구하기

 

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j]

 

 

 

 

2. 모든 점에 대해 (x1, y1)부터 (x2, y2)의 합 구하고, 최댓값 갱신

 

 

dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]

 

 

 모든 점에 대해 탐색을 하기 위해 4중 for문을 통해, x2 > x1, y2 > y1 점에 대해 위 DP 식을 통해 누적합 값을 구해주고, 최댓값을 갱신했다.

 

 

 

 

 

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		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[][] arr = 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++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int[][] dp = new int[N + 1][M + 1]; //행렬 (i, j)까지의 합
		
		//행렬(1,1)~(i, j)까지의 합 구하기
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= M; j++) {
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
			}
		}
		
		//행렬(x1,y1)~(x2, y2)까지의 합 구하기
		int max = Integer.MIN_VALUE;
		
		for(int x1 = 1; x1 <= N; x1++) {
			for(int y1 = 1; y1 <= M; y1++) {
				for(int x2 = x1; x2 <= N; x2++) {
					for(int y2 = y1; y2 <= M; y2++) {
						max = Math.max(max, dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]);
					}
				}
			}
		}
		
		System.out.println(max);
	}

}

 

 

 

 O(N^2 * M^2)으로 당연히 비효율적이고, 채점상으로 1000ms 대의 시간이 나오는 풀이다.

하지만 N과 M이 200미만이고, x2 > x1, y2 > y1인 모든 점에 대해 구하고, 문제의 제한시간이 2초이니 통과가 된다. 만약 1초였다면 이 풀이는 시간초과로 통과를 못했을 것이다..

 

 

 

 

 

[방법2] O(N ^3) 풀이 => 300ms대

 

 

1. dp[i][j] : 행 별 누적합 구하기

 

행 별로 dp[i][0]~ dp[i][M] 까지의 누적합을 구해나간다. 

 

 

 

2. 행의 부분 길이 합을 구하고, 모든 행에 대해 그 합을 쌓기

 

 한 행의 모든 부분 길이 합을 구하기 위해 2중 for문으로 i < j인 값에 대해, 한 행의 j열까지의 합에 i열까지의 합을 빼준다.

 

 그리고 모든 행을 한 줄씩 쌓아나가며, 최댓값을 갱신한다. 만약 현재 행의 부분 길이 합이 지금까지의 누적합보다 크다면, 누적합을 현재 행의 부분 길이 합으로 바꿔준다. 이렇게 하면 이전처럼 또 안에 2 for문으로 가능한 모든 (y1~y2)의 누적합을 구할 필요가 없어진다!

 

 

 

이렇게 하면 O(N^3)으로 풀이가 가능해진다.

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		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[][] arr = 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++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int[][] dp = new int[N + 1][M + 1]; //행렬 (i, 0)~(i, j)까지의 합
		
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= M; j++) {
				dp[i][j] = dp[i][j - 1] + arr[i][j];
			}
		}
		
		int max = Integer.MIN_VALUE; //정답 : 부분 행렬 합의 최대
		
		for(int i = 1; i <= M; i++) {
			for(int j = i; j <= M; j++) {
				int sum = 0;
				for(int k = 1; k <= N; k++) { //행 늘려감
					int row = dp[k][j] - dp[k][i - 1]; //한줄
					sum += row; //한줄 더함
					if(row > sum) sum = row; //한줄 이 더 크면, 이전 기록 버리고 sum을 갱신
					max = Math.max(max, sum); //최댓값 갱신
				}
			}
		}
		
		System.out.println(max);
	}

}

 

 

 

 

 

결과

 

[방법1] O(N^4) 풀이 : 1000ms대

[방법2] O(N^3) 풀이 : 300ms대

 

 

 

 

 

배운점