[백준 C] 23562 ㄷ 만들기
문제
2021년, 냅다 ㄷ 만들기는 한국인의 기본 소양이 되었다. 우리는 앞에 놓여있는 모눈종이에 냅다 ㄷ을 그리려 한다.
ㄷ 모양은 정사각형 7개를 붙인 형태로 정의한다. 다음은 각각 일 때의 ㄷ 모양이다.
ㄷ 모양이 아닌 것의 예는 다음과 같다.
모눈종이의 일부 칸에는 이미 검은색이 칠해져 있다. 흰색 칸을 검은색으로 칠하는 데 드는 비용은 , 검은색 칸을 지워서 흰색 칸으로 만드는 데 드는 비용은 다. 검은색 칸들이 ㄷ 모양을 이룰 수 있도록 하기 위해 드는 최소 비용을 구하는 프로그램을 작성하자.
ㄷ 모양의 위치와 크기에는 제한이 없지만, 뒤집거나 돌릴 수는 없으며, 모눈종이를 벗어나도 안 된다. 또한, 모든 검은색 칸은 ㄷ 모양에 포함되어야 하고, ㄷ 모양에 포함되지 않는 칸은 모두 흰색이어야 한다.
입력
첫 번째 줄에 모눈종이의 크기 이 주어진다.
두 번째 줄에 칸의 색깔을 바꾸는 데 드는 비용 가 주어진다.
다음 개의 줄에 길이 인 문자열이 주어진다. #은 검은색으로 칠해진 칸, .은 흰색 칸을 의미한다.
출력
첫 번째 줄에 ㄷ 모양을 만들 수 있는 최소 비용을 출력한다.
https://www.acmicpc.net/problem/23562
풀이
만들 ㄷ 의 크기는 3k x 3k (k=1,2,'') 이므로.. 맵크기에 맞게 k를 제한한뒤,
좌상단좌표를 (x,y)로 기준좌표로삼아, 오른쪽, 아래로 3k씩탐색하는 좌표가 (xx,yy)로 보아,
-
(xx,yy)가 가능한공간 (3k x 3k)에 모든 흰색->검은색 비용을 계산합니다.
-
동시에, 3k x 3k공간에서 모든 검은색갯수를 셉니다.
-
모두 세고나면, 3k x 3k 밖에있는 검은색갯수를 알수있고, 이를 모두 흰색으로 바꿔주어야하므로, 비용을 계산합니다.
-
ㄷ에서 실제로 흰색이 필요한공간 (41~52라인) 에서 위 1번과정에서 흰색을 강제로 바꿨으니, 다시 이 비용을 뺍니다.
-
또, 검은색->흰색 비용을 계산합니다.
마지막으로 이것이 최솟값이면 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;
}
Author And Source
이 문제에 관하여([백준 C] 23562 ㄷ 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cldhfleks2/23562저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)