[코딩테스트] 백준(BAEKJOON) - 구간 합 구하기 5(Java, 11660번)

네 오늘의 두 번째 문제 구간 합 구하기 5 문제입니다.

 

사실 이문제는 저혼자의 힘으로 풀지는 못하고 아침에 풀이를 보고 저녁에 복습겸 다시 풀었습니다.

 

다행히 답은 나왔는데 여기서 또 문제가 있었습니다 ㅠㅠ

이래서 언제 코테 마스터가 될지 흑흑

 

문제만나 보시죠~

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

11660번: 구간 합 구하기 5

간단하게 하나씩 더하면 되지 않아?! 라고 생각했지만 아니었습니다. ㅠㅠ

 

제가 작성한 코드를 보여드리고 다음에 설명을 간단하게 붙이겠습니다.

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


public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
			BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st=new StringTokenizer(bf.readLine());
			StringBuilder sb=new StringBuilder();
			
			//String line=bf.readLine();
			//int N=Integer.parseInt(line.split(" ")[0]);
			//int M=Integer.parseInt(line.split(" ")[1]);
			
			int N=Integer.parseInt(st.nextToken());
			int M=Integer.parseInt(st.nextToken());
			
			int table[][]=new int[N+1][N+1];
			int dp[][]=new int[N+1][N+1];
			
			int answer[]=new int[M+1];
			for(int i=1;i<=N;i++)
			{
				//String xy=bf.readLine();
				st=new StringTokenizer(bf.readLine());
				for(int j=1;j<=N;j++)
					table[i][j]=Integer.parseInt(st.nextToken());

			}
						
			for(int i=1;i<=N;i++)
			{
				for(int j=1;j<=N;j++)
				{
					dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+table[i][j];				
				}
			}
			
			for(int i=1;i<M+1;i++)
			{
				//String value=bf.readLine();
				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 ans=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
				sb.append(ans+"\n");
			}
			
			System.out.println(sb);

			
	}

}

 

① table을 이용해서 입력받은 값들을 저장

② dp array에 기존에 table array를 통해 구간의 합 계산 및 저장

③ dp array를 이용해 특정 구간의 합을 도출

 

일단 머리로는 이렇게 간단하지만

실제 코딩으로 볼까요?

 

① table을 이용해서 입력받은 값들을 저장

제가 작성한 코드 부분을 보시면 알겠지만 저는 처음에 String 형식으로 입력받고

split을 이용해 table array에 저장했습니다.

 

근데 이렇게 하면 시간초과가 나와서 너무 당황했습니다.

(StringTokenizer와 StringBuilder에 대한 공부를 해야겠습니다.)

table은 이렇게 저장하면 되겠습니다.

 

② dp array에 기존에 table array를 통해 구간의 합 계산 및 저장

이제 dp array를 만들어야 합니다.

0,0~ M,M까지의 합을 각각 구해주시면 되겠습니다.

이해가 되실까요..?

즉 전체의 합을 구하기 위해서는 x-1,y의 합과 x,y-1의합을 구한뒤 arr(x,y)의 값을 더하고 두 번째 사진처럼 겹치는 부분을 빼준다~ 가 핵심이되겠습니다.

 

공식으로 간단하게 표현하자면

DP(M,N)=DP(M-1,N)+DP(M,N-1)-DP(M-1,N-1)+arr(M,N)

이 되겠습니다.

 

이렇게 DP테이블을 채웠습니다.

 

③ dp array를 이용해 특정 구간의 합을 도출

이제 마지막으로 구간에 따라 값을 구해보겠습니다.

기존의 만든 DP테이블을 이용하겠습니다.

예 요것은 제가 예시를 위해 그린 M이 5일경우입니다.

여기서 (3,3)~(5,5)까지의 구간합을 구하고싶다는 가정하에 그렸습니다.

 

그럼 여기서 x1=3, y1=3, x2=5, y2=5가 되겠습니다.

 

먼저 가장 끝 넓이인 x2, y2의 dp테이블(DP(x2,y2)) 값에서

 

파란색 넓이를 빼주고, dp(x1-1,y2)

빨간색 넓이를 빼주면 dp(x2,y1-1)

 

빗금쳐진 부분이 2번 빠지게됩니다.

그렇기 때문에 빗금쳐진 부분 dp(x1-1,y1-1)을 한 번 더해주겠습니다.

 

그렇기에 구간 합에 대한 공식은

DP(x2,y2)-DP(x1-1,y2)-DP(x2,y1-1)+DP(x1-1,y1-1)

이 되겠습니다.

 

쓰면서도 몇 번이나 헷갈렸네요 후우

 

오늘은 이렇게 마무리 지어보고자 합니다.

 

문제를 보자마자 이걸 이렇게 생각해내야된다는게 저는 안되네요 하하😂😂

그래도 포기하지 않고 열심히 해봅시닷!

 

감사합니다.