22979번 - 색종이 붙이기 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 512 MB | 137 | 13 | 11 | 39.286% |
문제
현욱은 학교 미술 과제로 여러 장의 색종이를 붙여 만든 작품을 내려고 한다. 현욱은 우선 색종이를 붙일 수 있는 위아래로 $N$칸, 좌우로 $M$칸 크기($ 1 \le N, M \le 2000 $)인 직사각형 모양의 모눈 종이를 준비했다.
현욱은 이 모눈 종이의 일부 칸에 색칠을 하고, 나머지 칸들은 색종이를 붙여서 채우려고 한다. 현욱은 가로, 세로 크기가 모눈 크기의 배수가 되는 여러 가지 종류의 색종이를 가지고 있다. 이 중에서 한 종류의 색종이를 골라 그 색종이만을 이용해서 모든 칸을 채우려고 하는데, 다음 조건을 만족하면서 색종이를 붙이려고 한다.
- 색종이는 모눈 칸에 정확히 맞춰서 붙여야 하며, 회전할 수 없다.
- 색종이끼리는 서로 겹쳐 붙여도 되지만, 기존에 색을 칠해둔 칸과 겹쳐 붙여서는 안 된다.
- 색칠되지 않은 모든 칸은 한 장 이상의 색종이가 덮어야만 한다.
현욱은 이런 조건을 만족하는 색종이의 종류가 얼마나 다양한지 궁금해졌다. 현욱을 도와 주어진 조건을 만족하는 색종이 크기의 경우의 수를 계산해보자.
입력
첫 줄에 종이의 크기 $N$, $M$ 이 공백으로 구분되어 주어진다($ 1 \le N, M \le 2000 $).
둘째줄부터 $N$줄에 걸쳐 모눈 종이의 현재 상태가 주어진다. '.'의 경우 색이 칠해지지 않은 칸, '#'의 경우 색이 칠해진 칸이다. 색이 칠해지지 않은 칸은 반드시 하나 이상 존재한다.
출력
첫째 줄에 문제에서 제시된 조건을 만족하는 색종이의 크기가 몇 종류인지 출력한다.
서브태스크 1 (40점)
$ 1 \le N, M \le 15 $
서브태스크 2 (16점)
$ 1 \le N, M \le 100 $
서브태스크 3 (14점)
$ 1 \le N, M \le 400 $
서브태스크 4 (55점)
추가 제한 없음
예제 입력 1
3 3 ..# ... #..
예제 출력 1
4
1x1, 1x2, 2x1, 2x2 의 4종류의 색종이가 조건을 만족한다. 색종이를 회전할 수 없기 때문에 1x2 크기와 2x1 크기는 서로 다른 종류로 생각한다.
예제 입력 2
8 9 ......... ......... ......... ...#..... .....#... ....#.... ......... .........
예제 출력 2
4
예제 입력 3
9 9 ######... ######... ######... #........ #.....### #.....### #####.... #####.... #####....
예제 출력 3
9
예제 입력 4
5 5 ..... ....# ...## ..### .####
예제 출력 4
1
출처
Contest > BOJ User Contest > 소프트콘 > 제3회 소프트콘 G번
Contest > Open Cup > 2021/2022 Season > Stage 4: Grand Prix of Korea I번
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호