문제

https://www.acmicpc.net/problem/14500

해설

테트로미노를 N*M 종이 위에 하나 두었을 때, 얻을 수 있는 합의 최대를 구해야 합니다.
문제에서 주어진 테트리미노는 5개이며, 각 테트리미노를 회전하거나 대칭시켜서 만들 수 있는 형태는 총 19가지입니다.

• I 형태 : 2가지
• O 형태 : 1가지
• L 형태 : 8가지
• S 형태 : 4가지
• T 형태 : 4가지

시간복잡도 계산

$4 \leq N,M \leq 500$ 이므로 최대 uptime은 대략 $19 \times N \times M \times 4 \leq 10^{18}$ 로, Brute-force로도 충분히 해결 가능합니다.

구현

19가지 경우의 형태를 상대 위치를 사용한 배열로 만들고 이를 모든 위치에 놓아보면서 확인해보면 됩니다.

소스 코드

http://boj.kr/9fd593147b794c3ea5b2848f4da39153

---

참고

• BOJ 14500 · 테트로미노 : 그림으로 잘 설명되어 있습니다.