글 읽기 - 입력값제한확인했으나..반례를 모르겠습니다. 코드설명있음

cldhfleks2 2년 전 0

만들 ㄷ 의 크기는 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를 출력...

맵전체가 검은색일때, 흰색일때 확인해보았고..

n,m최대범위인 20일대 최소인 3일때 각각 확인했을때 문제없었습니다..

아래는 제가 확인한 입력값들입니다..

============================================================

3 3
2 5
#.#
.#.
#.#

6 7
10 15
.#####.
.#####.
.#.....
.#.....
.#####.
.#####.

8 8
1000 1
..#..#..
.#..#..#
#..#..#.
..#..#..
.#..#..#
#..#..#.
..#..#..
.#..#..#

8 8
3 5
########
########
########
########
########
########
########
########

6 7
3 5
...####
...##..
...####
......#
#######
#######

20 20
3 5
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################

6 20
3 5
#...................
....................
....................
....................
....................
...................#

============================================================

이 입력들외에 문제가되는 반례가 있을까요?

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
//맵크기 n x m 
//map : 검은칸은 b 흰색칸은 a값대입
//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
				//printf("==================================================%d=%d, %d\n", k, x, y);
				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] == a) { //흰칸을 검은칸으로
							//printf(">> 흰->검 %d,%d\n", xx, yy);
							price += a;
						}
						else if (map[xx][yy] == b) //남은 검은칸의 갯수를 셈
							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] == a) { //흰칸: 1번에서 필요없는비용을 추가했으니, 다시 빼줌
							//printf(">> >> 흰 다시빼줌 %d,%d\n", xx, yy);
							price -= a; 
						}
						else if (map[xx][yy] == b){ //검은칸 : 흰칸으로 칠하는 비용추가
							//printf(">> >> 검->흰 %d,%d\n", xx, yy);
							price += b; 
						}
					}
				}

				//최솟값만 res 에 갱신
				if (res > price) { res = price; //printf(">> k%d x:%d y:%d  lessBlackCnt%d\n", k, x, y, lessBlackCnt);
				}
			}
		}

	}

	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] = b; //검은칸 에는 b
				blackCnt++; //검은칸 갯수를 셈
			}
			else
				map[i][j] = a; //흰칸에는 a
		}
	}

}

int main(void) {
	func();

	return 0;
}

cldhfleks2 2년 전 0

입력받은 # 와 . 을 바로 a, b 로 대입해서 오류가났었네요..

a == b 이면 이후에 해당칸이 검은칸인지 백칸인지 비교할때 오류가나네용

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

입력값제한확인했으나..반례를 모르겠습니다. 코드설명있음

cldhfleks2 2년 전 0

cldhfleks2 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말