cldhfleks2   8달 전

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

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

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

cldhfleks2   8달 전

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

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

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