시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 170 | 93 | 77 | 50.993% |
영선이는 방 바닥에 타일을 놓으려고 한다. 바닥은 직사각형 모양이며 1×1 크기의 정사각형으로 나누어져 있다. 타일의 크기는 1×k 크기이며, k는 양의 정수이다. 타일은 바닥의 변과 평행하게 놓아야 하며, 칸의 경계와 변이 일치해야 한다. 또, 타일은 겹쳐서 놓을 수 없다.
영선이의 방에는 기둥이 놓여져 있는데, 기둥의 크기는 1×1 이다. 또, 타일은 기둥이 놓여진 칸에 놓여질 수 없다.
방 바닥에 놓을 수 있는 타일의 최소 개수를 구하는 프로그램을 작성하시오. 이때, 바닥에 빈 칸이 있으면 안 된다.
첫째 줄에 방의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 10)
둘째 줄부터 방 바닥의 모양이 주어진다. '.'은 빈 칸, '#'은 기둥이 놓여진 칸이다.
첫째 줄에 방 바닥을 모두 채우는데 필요한 타일의 최소 개수를 출력한다.
5 5 ..... ..... ..... ..... .....
5
6 7 ....... .#..##. .#..... .#####. .##..#. ....###
7
4 4 #### #### #### ####
0
6 6 ...#.. ##.... #.#... .#.... ..#... ..#..#
9