문제 출처: https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
1X1 정사각형 네개를 이어 붙혀서 만들 수 있는 모양으로 칸을 덮었을 때 덮혀진 칸들의 값의 총합이 가장 클 때를 구하는 문제입니다. 종만북에서 BOARDCOVER문제를 풀고 생각이 나서 풀었습니다. 종만북을 보기 전에는 구현이 복잡할 것같아서 그냥 포기했었는데 BOARDCOVER에서 모양을 배열로 저장하는 방법을 통해서 쉽게 구현할 수 있었습니다. 전형적인 부루트 포스문제로 4개의 정사각형의 만들 수 있는 모양 총 19개이며 최대 500X500개의 칸에 대해서 검사를 되고 범위 조건에 의해 4 X 19 X 500 X 500 번의 수행보다 적은 수행 시간으로 구할 수 있습니다.
'문제 해결 > BOJ' 카테고리의 다른 글
| [BOJ] 일요일 아침의 데이트 (0) | 2023.02.02 |
|---|---|
| [백준] 10986번 나머지 합 - python (1) | 2022.09.29 |
| [BOJ] 3980번 선발 명단 (0) | 2019.08.20 |
| [BOJ] 1436번 영화감독 숌 (0) | 2019.08.18 |
| [BOJ] 15683 감시 (0) | 2019.08.17 |