백준 11660번: 구간 합 구하기 5 [구간합][누적합][DP] -Java

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

11660번: 구간 합 구하기 5

 

[구간 합 구하기 3]에서 더 업그레이드 된 문제. 2차원 배열이 되었다..!!

 

<첫 번째 시도 - 시간초과>

행별로 누적합을 구한다음 그 행만큼 for문 돌려서 범위지정하여 최종합을 구하는 방식이다.

O(N*M)인데 시간초과 났다. 100,000 * 1024 하면 딱 1억번정돈데.. 걸렸넹 ㅠㅋ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		//System.setIn(new FileInputStream("Test.txt"));
		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 sum[][] = 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++) {
				int num = Integer.parseInt(st.nextToken());
				sum[i][j] = sum[i][j-1]+num;
			}
		}
		
//		for (int i = 0; i < sum.length; i++) {
//			for (int j = 0; j < sum.length; j++) {
//				System.out.print(sum[i][j]+ " ");
//			}
//			System.out.println();
//		}
		
		for (int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			
			int sx = Integer.parseInt(st.nextToken());
			int sy = Integer.parseInt(st.nextToken());
			int ex = Integer.parseInt(st.nextToken());
			int ey = Integer.parseInt(st.nextToken());
			
			int result = 0;
			
			for (int i = sx; i <= ex; i++) {
				result += sum[i][ey] - sum[i][sy-1];
			}
			
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
			bw.write(result+"\n");
			bw.flush();
			
		}
	}

}

 

 

<두 번째 시도 - 맞았습니다!>

 

패드로 끄적인 내용을 복붙..

 

728x90

요는

1. 2차원배열 누적합 구하기

2. 누적합배열을 이용하여 값 도출하기

 

1의 누적합배열 구하는 방법은 1.1부터 특정 지점까지 네모를 그린다치고 거기에 포함된 모든 값을 다 더하는 경우이다.

 

for문을 또 돌지 않아도 되기때문에 O(M) = O(1)로 끝난다.

728x90

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		//System.setIn(new FileInputStream("Test.txt"));
		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 map[][] = new int[N+1][N+1];
		int sum[][] = new int[N+1][N+1]; //1부터 네모범위 구간합
		
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <=N; j++) {
				int num = Integer.parseInt(st.nextToken());
				map[i][j] = num;
				sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+num;
			}
		}
		
//		for (int i = 0; i < sum.length; i++) {
//			for (int j = 0; j < sum.length; j++) {
//				System.out.print(sum[i][j]+ "\t");
//			}
//			System.out.println();
//		}
		
		for (int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			
			int sx = Integer.parseInt(st.nextToken());
			int sy = Integer.parseInt(st.nextToken());
			int ex = Integer.parseInt(st.nextToken());
			int ey = Integer.parseInt(st.nextToken());
			
			int result = 0;
			
//			//행 구간합일 경우 행만큼 돌아서 sum
//			for (int i = sx; i <= ex; i++) {
//				result += sum[i][ey] - sum[i][sy-1];
//			}
			
			result = sum[ex][ey] - sum[sx-1][ey]-sum[ex][sy-1]+sum[sx-1][sy-1];
			
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
			bw.write(result+"\n");
			bw.flush();
			
		}
	}

}