[백준 25682번 C/C++] 체스판 다시 칠하기 2

 

[백준 25682번 C/C++] 체스판 다시 칠하기 2

 

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

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

---

 

 

해결전략

 

누적합, 동적 프로그래밍 Dynamic Programming DP

 

체스판 위에 k x k 크기의 정사각형을 놓았을 때, 정사각형 내의 체스판 칸 색깔을 바꿔서 모두 같은 색으로 만드는 데 필요한 최소 변경 횟수를 찾는다.

---

 

 

처음 시도한 코드 - 98%에서 실패

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int n, m, k;
vector<vector<char>> v;
vector<vector<int>> change, dp;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m >> k;
	v.resize(n, vector<char>(m));
	change.resize(n, vector<int>(m));
	dp.resize(n, vector<int>(m));
	for(int y = 0; y < n; y++){
		for(int x = 0; x < m; x++){
			cin >> v[y][x];
		}
	}

	int paint = 2147483647;
	if (v[0][0] == 'B')
	{
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++) 
			{
				if ((y + x) % 2 == 0) {
					if (v[y][x] == 'B') change[y][x] = 1;
				}
				else {
					if (v[y][x] == 'W') change[y][x] = 1;
				}
			}
		}

		dp[0][0] = change[0][0];
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++)
			{
				if (y == 0 && x == 0) continue;
				if (y >= 1 && x == 0) dp[y][0] = dp[y - 1][0] + change[y][x];
				else if (y == 0 && x >= 1) dp[0][x] = dp[0][x - 1] + change[y][x];
				else 
					dp[y][x] = dp[y - 1][x] + dp[y][x - 1] - dp[y - 1][x - 1] + change[y][x];

				if (y >= k - 1 && x >= k - 1)
				{
					int cnt;
					if (y == k - 1 && x == k - 1) {
						cnt = dp[y][x];
					}
					else if (y == k - 1 && x > k - 1){
						cnt = dp[y][x] - dp[y][x - k];
					}
					else if (y > k - 1 && x == k - 1) {
						cnt = dp[y][x] - dp[y - k][x];
					}
					else{
						cnt = dp[y][x] - dp[y - k][x] - dp[y][x - k] + dp[y - k][x - k];
					}

					int total = k * k;
					paint = min(paint, min(cnt, total - cnt));
				}
			}
		}			
	}
	else
	{
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++)
			{
				if ((y + x) % 2 == 0) {
					if (v[y][x] == 'W') change[y][x] = 1;
				}
				else {
					if (v[y][x] == 'B') change[y][x] = 1;
				}
			}
		}

		dp[0][0] = change[0][0];
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++)
			{
				if (y == 0 && x == 0) continue;
				if (y >= 1 && x == 0) dp[y][0] = dp[y - 1][0] + change[y][x];
				else if (y == 0 && x >= 1) dp[0][x] = dp[0][x - 1] + change[y][x];
				else 
					dp[y][x] = dp[y - 1][x] + dp[y][x - 1] - dp[y - 1][x - 1] + change[y][x];

				if (y >= k - 1 && x >= k - 1)
				{
					int cnt;
					if (y == k - 1 && x == k - 1) {
						cnt = dp[y][x];
					}
					else if (y == k - 1 && x > k - 1) {
						cnt = dp[y][x] - dp[y][x - k];
					}
					else if (y > k - 1 && x == k - 1) {
						cnt = dp[y][x] - dp[y - k][x];
					}
					else {
						cnt = dp[y][x] - dp[y - k][x] - dp[y][x - k] + dp[y - k][x - k];
					}

					int total = k * k;
					paint = min(paint, min(cnt, total - cnt));
				}
			}
		}
	}

	cout << paint << "\n";
	
	return 0;
}

 

---

 

정답 코드

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int n, m, k; // n과 m은 체스판의 크기, k는 바꿔야 하는 정사각형의 크기
vector<vector<int>> black, white; // black과 white는 각각 검은색과 흰색 칸의 개수를 나타내는 2차원 벡터

int main(){
	ios::sync_with_stdio(false); 
	cin.tie(0); cout.tie(0); 

	cin >> n >> m >> k;
	black.resize(n+1, vector<int>(m+1)); 
	white.resize(n+1, vector<int>(m+1)); 

	char input; 
	for(int y = 1; y <= n; y++){
		for(int x = 1; x <= m; x++){
			cin >> input; 
			
			// 누적 합을 계산. (y, x) 위치까지의 검은색과 흰색 칸의 개수를 구한다.
			black[y][x] = black[y - 1][x] + black[y][x - 1] - black[y - 1][x - 1];
			white[y][x] = white[y - 1][x] + white[y][x - 1] - white[y - 1][x - 1];

			// (y, x) 위치의 칸 색깔이 검은색인지 흰색인지를 확인하고, 해당 칸의 개수를 증가시킨다.
			if ((y + x) % 2 == 0) {
				if (input == 'B') white[y][x]++;
				else black[y][x]++;
			}
			else {
				if (input == 'W') white[y][x]++;
				else black[y][x]++;
			}
		}
	}

	int cnt = k * k; // 최소 변경 횟수를 저장하는 변수. 초기값은 k*k로 설정
	for (int y = k; y <= n; y++) {
		for (int x = k; x <= m; x++) 
        {
			// (y, x)를 우측 하단 꼭짓점으로 하는 kxk 크기의 정사각형 내의 검은색과 흰색 칸의 개수를 구한다.
			int blackCnt = black[y][x] - black[y - k][x] - black[y][x - k] + black[y - k][x - k];
			int whiteCnt = white[y][x] - white[y - k][x] - white[y][x - k] + white[y - k][x - k];

			cnt = min(cnt, min(blackCnt, whiteCnt)); // 최소 변경 횟수를 갱신. 검은색과 흰색 칸의 개수 중 작은 것을 선택.
		}
	}

	cout << cnt << "\n"; // 최소 변경 횟수를 출력
    
	return 0;
}

 

 

 

 

---