[JAVA] B11660_구간합구하기 5

11660번: 구간 합 구하기 5

틀린 코드 (시간초과) 

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

public class B11660_구간합구하기2 {

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int [][] arr = new int[N+1][N+1];
		int [][] S = new int[N+1][N+1];
		for(int i=1;i<N+1;i++) {
			st = new StringTokenizer(bf.readLine());
			for(int j =1;j<N+1;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				S[i][j] = S[i][j-1] + arr[i][j];  //누적합
			}
		}
		System.out.println(Arrays.deepToString(arr));
		System.out.println(Arrays.deepToString(S));
	}

}

 

생각해본 방법

 

1. 도형을 나눠서 빼고 더하고

대충 그린 그림 :: 결론은 큰데에서 두개빼고 겹친것을 더하면 원하는 도형만 남는다!

(3,4) 빨강 = 주황 - (노랑+초록) + (노랑과 초록의 합집합 = 1,1)

문제는 각 자리의 합 (누적합)을 구하고 이 방법을 실행하는 것이었다.

(모름)

정답 => 다이나믹 알고리즘을 쓰자!

 

 

 🔔🔔🔔🔔🔔🔔🔔🔔🔔🔔

위의 두가지의 생각을 합치면 정답이 된다... 

정답 코드  : 다이나믹 알고리즘 사용 

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

public class B11660_구간합구하기5 {

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int [][] arr = new int[N+1][N+1];
		
		for(int i=1;i<N+1;i++) {
			st = new StringTokenizer(bf.readLine());
			for(int j =1;j<N+1;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int dp[][] = new int[N+1][N+1];
		for(int x=1;x<N+1;x++) {
			for(int y =1;y<N+1;y++) {
				dp[x][y] = dp[x][y-1]+dp[x-1][y]-dp[x-1][y-1] +arr[x][y];
			}
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(bf.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 sum = dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];
			
			System.out.println(sum);
		}	
	}
}