[백준 C] 23562 ㄷ 만들기

문제

2021년, 냅다 ㄷ 만들기는 한국인의 기본 소양이 되었다. 우리는 앞에 놓여있는 $n \times m$ 모눈종이에 냅다 ㄷ을 그리려 한다.

ㄷ 모양은 $k \times k$ 정사각형 7개를 붙인 형태로 정의한다. 다음은 각각 $k=1, k=2$일 때의 ㄷ 모양이다.

ㄷ 모양이 아닌 것의 예는 다음과 같다.

모눈종이의 일부 칸에는 이미 검은색이 칠해져 있다. 흰색 칸을 검은색으로 칠하는 데 드는 비용은 $a$, 검은색 칸을 지워서 흰색 칸으로 만드는 데 드는 비용은 $b$다. 검은색 칸들이 ㄷ 모양을 이룰 수 있도록 하기 위해 드는 최소 비용을 구하는 프로그램을 작성하자.

ㄷ 모양의 위치와 크기에는 제한이 없지만, 뒤집거나 돌릴 수는 없으며, 모눈종이를 벗어나도 안 된다. 또한, 모든 검은색 칸은 ㄷ 모양에 포함되어야 하고, ㄷ 모양에 포함되지 않는 칸은 모두 흰색이어야 한다.

입력

첫 번째 줄에 모눈종이의 크기 $n, m$이 주어진다.

두 번째 줄에 칸의 색깔을 바꾸는 데 드는 비용 $a,b$가 주어진다.

다음 $n$개의 줄에 길이 $m$인 문자열이 주어진다. #은 검은색으로 칠해진 칸, .은 흰색 칸을 의미한다.

출력

첫 번째 줄에 ㄷ 모양을 만들 수 있는 최소 비용을 출력한다.

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

풀이

만들 ㄷ 의 크기는 3k x 3k (k=1,2,'') 이므로.. 맵크기에 맞게 k를 제한한뒤,

좌상단좌표를 (x,y)로 기준좌표로삼아, 오른쪽, 아래로 3k씩탐색하는 좌표가 (xx,yy)로 보아,

1. (xx,yy)가 가능한공간 (3k x 3k)에 모든 흰색->검은색 비용을 계산합니다.

2. 동시에, 3k x 3k공간에서 모든 검은색갯수를 셉니다.

3. 모두 세고나면, 3k x 3k 밖에있는 검은색갯수를 알수있고, 이를 모두 흰색으로 바꿔주어야하므로, 비용을 계산합니다.

4. ㄷ에서 실제로 흰색이 필요한공간 (41~52라인) 에서 위 1번과정에서 흰색을 강제로 바꿨으니, 다시 이 비용을 뺍니다.

5. 또, 검은색->흰색 비용을 계산합니다.

마지막으로 이것이 최솟값이면 res에 저장, 최종적으로 결정된 res출력.

여기서 실수한점은,
처음에 입력받은 # 과 . 을 바로 b 와 a 값으로 map[][] 에 대입한것이 큰 실수였다. 하루이틀 맞왜틀하다가 a == b 인 반례를 확인해서
b대신 -1, a 대신 -2를 넣어서 검은칸, 흰칸을 확실히 구분했다..

따라서 빨간부분도 전부 == a, == b로 작성했었는데 이것이 오류이다..

한두단계 빨리 건너띄려고하다가 오류가났던것..

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
//맵크기 n x m 
//map : 검은칸은 -1 흰색칸은 -2값대입
//a : 흰색을 검정으로 칠하는비용
//b : 검정을 흰색으로 칠하는비용
//blackCnt : 모든 검은칸갯수 (ㄷ자에 모든 검은칸이 포함되어야한다.)
int n, m, a, b, **map, blackCnt=0;
void func();
void input();

void func() {
	input();
	int maxSize = n >= m ? m : n; //n과 m중 최솟값
	int res = 0x7fffffff;
	for (int k = 1; 3 * k <= maxSize; k ++) {
		
		//시작위치 x,y(좌상단좌표)를 정함
		int size = 3 * k;
		for (int x = 0; x + size <= n; x++) { //올바른 좌표범위 (0,0)~(n-1,m-1)
			for (int y = 0; y + size <= m; y++) { //ㄷ의 크기는 3k x 3k
				int price = 0; //색을 다시 칠하는 비용
				int lessBlackCnt = blackCnt; //모눈종이의 모든 검은칸의 갯수 - 3k x 3k공간에서 확인된 검은칸의갯수.
											 //즉 남은 검은색갯수
				//1. 3k x 3k칸을 모두 검은색으로 칠하는 비용 계산
				for (int xx = x; xx < x + size; xx++) { //ㄷ내부의 모든 모눈종이를 확인
					for (int yy = y; yy < y + size; yy ++) { //(x,y)~(x+2k,y+2k)확인
						if (map[xx][yy] == -2) { //흰칸을 검은칸으로
							price += a;
						}
						else if (map[xx][yy] == -1) //남은 검은칸의 갯수를 셈
							lessBlackCnt--;
					}
				}
				//2. 3k x 3k이외의 모든 모눈종이칸에있는 검은색을 흰색으로 다시칠해야함
				price += lessBlackCnt * b; 
				
				//3. 흰색칸이어야 하는곳의 비용 계산
				for (int xx = x + k; xx < x + size - k; xx++) {
					for (int yy = y + k; yy < y + size; yy++) {
						if (map[xx][yy] == -2) { //흰칸: 1번에서 필요없는비용을 추가했으니, 다시 빼줌
							price -= a; 
						}
						else if (map[xx][yy] == -1){ //검은칸 : 흰칸으로 칠하는 비용추가
							price += b; 
						}
					}
				}

				//최솟값만 res 에 갱신
				if (res > price)
					res = price; 
			}
		}

	}

	printf("%d", res);
}

void input() {
	scanf("%d%d%d%d", &n, &m, &a, &b);

	map = new int* [n];
	for (int i = 0; i < n; i++) {
		map[i] = new int[m];
		char _;
		scanf("%c", &_); //줄바꿈문자지움
		for (int j = 0; j < m; j++) {
			scanf("%c", &_);
			if (_ == '#') {
				map[i][j] = -1; //검은칸에는 -1
				blackCnt++; //검은칸 갯수를 셈
			}
			else
				map[i][j] = -2; //흰칸에는 -2
		}
	}

}

int main(void) {
	func();

	return 0;
}