백준 25682 - 체스판 다시 칠하기 2 (누적합, JAVA)

참조 목록 

https://nahwasa.com/entry/%EB%88%84%EC%A0%81-%ED%95%A9prefix-sum-2%EC%B0%A8%EC%9B%90-%EB%88%84%EC%A0%81%ED%95%A9prefix-sum-of-matrix-with-java

 

https://www.acmicpc.net/board/view/102646

 

https://gall.dcinside.com/mgallery/board/view/?id=ps&no=31079&page=1

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

 

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

25682번: 체스판 다시 칠하기 2

 

 

이거 시간 대충 676인데 400대로 줄일 수 있음

메모리는 괜찮은듯

 

아무튼 병신코드임

방법론
1. N+1 x M+1 char 배열 생성함, 이렇게 해야 누적합 짤 때 좀더 편함

2. B시작 W시작 누적합 배열도 만듬

3. min은 아무튼 최솟값 찾는거니 선언 정의

4. toggle toggle2 라는 불린 변수 쓰는데, 
toggle = true 는 홀수 번째 행, toggle = false 는 짝수 번째 행
toggle2 = true 는 홀수 번째 열, toggle2 = false 는 짝수 번째 열 을 의미함

5. 입력과 동시에 행 누적합을 구하는데, toggle toggle2 를 이용해서 해당 i,j 인덱스의 변수가 각각의 체스판에 대해서 알맞는 색인지 판별해서 B W 행 누적합 배열 작성, 알맞으면 이전 행 꺼 값으로 하고, 다르면 이전 행 값에 1씩 추가되는 형태임

6. 이중 포문 또 돌려서 열 누적합 구한다.

7. 2차원 누적합 함수 letsFindMinimum 를 쓰는데, B시작 W시작 체스판중 더 작은 값을 쓰므로 아무튼 Math.min 써서 리턴

8. K*K 크기 체스판에 대해서 고쳐야할 색 최솟값을 찾는다. 이는 이중 포문의 형태


만드는데 시간잡아먹었던 부분
1. 뭐 누적합을 어케 써야할지 감도 못잡음

2. 시간초과나서 봤더니 2차원 누적합 이라는게 있었음

 

방법론 핵심요약

- B로 시작하는 체스판, W로 시작하는 체스판에 대해서, 색이 다른 경우를 각각 누적합으로 쓴다.
- O(N^2) 으로 풀어야한다. 이를 위해서 2차원 누적합 방법론이 필요함

 

 

 

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

public class AAJB 
{
	static char[][] A;
	static int[][] blackStart;
	static int[][] whiteStart;
	static int N, M, K;
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		st = new StringTokenizer(input.readLine(), " ");
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		A = new char[N+1][M+1];
		
		blackStart = new int[N+1][M+1];
		whiteStart = new int[N+1][M+1];
		
		int min = Integer.MAX_VALUE;
		
		// toggle = true 는 홀수 번째 행
		// toggle = false 는 짝수 번째 행
		// toggle2 = true 는 홀수 번째 열
		// toggle2 = false 는 짝수 번째 열
		boolean toggle = true;
		boolean toggle2 = true;
		
		for (int i=1; i<=N; i++)
		{
			toggle2 = true;
			
			String s = input.readLine();
			
			for (int j=1; j<=M; j++)
			{
				char temp = s.charAt(j-1);
				
				A[i][j] = temp;
				
				if ( temp == 'B')
				{
					if ( toggle == true )
					{
						if ( toggle2 == true )
						{
							whiteStart[i][j] = whiteStart[i][j-1] + 1;
							blackStart[i][j] = blackStart[i][j-1];
						}
						else // toggle2 == false
						{
							blackStart[i][j] = blackStart[i][j-1] + 1;
							whiteStart[i][j] = whiteStart[i][j-1];
						}
					}
					else // toggle == false
					{
						if ( toggle2 == true )
						{
							blackStart[i][j] = blackStart[i][j-1] + 1;
							whiteStart[i][j] = whiteStart[i][j-1];
						}
						else // toggle2 == false
						{
							whiteStart[i][j] = whiteStart[i][j-1] + 1;
							blackStart[i][j] = blackStart[i][j-1];
						}
					}
				}
				else // temp == 'W'
				{
					if ( toggle == true )
					{
						if ( toggle2 == true )
						{
							blackStart[i][j] = blackStart[i][j-1] + 1;
							whiteStart[i][j] = whiteStart[i][j-1];
						}
						else // toggle2 == false
						{
							whiteStart[i][j] = whiteStart[i][j-1] + 1;
							blackStart[i][j] = blackStart[i][j-1];
						}
					}
					else // toggle == false
					{
						if ( toggle2 == true )
						{
							whiteStart[i][j] = whiteStart[i][j-1] + 1;
							blackStart[i][j] = blackStart[i][j-1];
						}
						else // toggle2 == false
						{
							blackStart[i][j] = blackStart[i][j-1] + 1;
							whiteStart[i][j] = whiteStart[i][j-1];
						}
					}
				}
				
				toggle2 = !toggle2;
			}
			
			toggle = !toggle;
		}
		
		for (int j=1; j<=M; j++)
		{
			for (int i=1; i<=N; i++)
			{
				blackStart[i][j] += blackStart[i-1][j];
				whiteStart[i][j] += whiteStart[i-1][j];
			}
		}
		
		for (int i=1; i<=N-K+1; i++)
		{
			for (int j=1; j<=M-K+1; j++)
				min = Math.min(min, letsFindMinimum(i,j));
		}
		
		output.write(min + "");
		output.close();
	}
	
	public static int letsFindMinimum (int a, int b)
	{
		int black = blackStart[a+K-1][b+K-1] 
				- ( blackStart[a-1][b+K-1] + blackStart[a+K-1][b-1]) + blackStart[a-1][b-1];
		int white = whiteStart[a+K-1][b+K-1] 
				- ( whiteStart[a-1][b+K-1] + whiteStart[a+K-1][b-1]) + whiteStart[a-1][b-1];
		
		return Math.min(black, white);
	}
}