시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 299 | 129 | 106 | 45.106% |
영과일은 학회방이 없어질 위기에 처했지만 우수한 학회원들의 실력을 인정받아 학회방을 다시 배정 받을 수 있었다! 이에 행복해진 영과일 총무부장 재현이는 새로운 마음으로 1 × 2, 1 × 1 타일을 구매하여 학회방 바닥을 모두 덮으려고 한다.
알뜰한 재현이를 도와 학회방 도면이 주어졌을 때 학회방 바닥을 모두 덮을 수 있는 최소의 타일 개수를 출력하는 프로그램을 작성하시오.
첫 번째 줄에 학회방 도면의 행의 수를 나타내는 N(1 ≤ N ≤ 50)과 열의 수를 나타내는 M(1 ≤ M ≤ 50)이 주어진다.
두 번째 줄부터 N개의 줄에 학회방 도면의 정보를 나타내는 길이가 M인 문자열이 주어진다. i+1번째 줄의 j번째 문자가 ‘.’ 일 경우 바닥, ‘X’ 일 경우 기둥을 나타낸다.
첫 번째 줄에 필요한 타일의 최소 개수를 출력한다.
3 4 .X.. ...X ...X
5
다음과 같이 덮으면 4개의 1 × 2 타일, 1개의 1 × 1 타일을 이용하여 학회방 바닥을 모두 덮을 수 있다.
University > 한양대학교 ERICA 캠퍼스 > Zero One Algorithm Contest 2018 H번