[백준 / BOJ] 14500 테트로미노

문제

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변

www.acmicpc.net

N*M크기의 종이에 숫자들이 쓰여있다.

이 종이에 테트로미노하나를 놓았을때, 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 찾는 문제다.

완전탐색으로 푼 문제다.

종이의 세로,가로가 각각 최대 500이며, 한번 탐색마다 (모든 폴리오미노를 본다했을때,) 40번이라고 하면, 총 탐색횟수는 250000*40 = 10000000가 되어서 시간초과를 피할수있다.

모든 칸을 하나씩보며, 해당 칸에서 테트로미노를 만들수있는 모든 경우의수를 다봐줬다.

X를 테트로미노가 있는 칸 이라고 할때,

OXO OXO

XXO OXX

OXO OXO ...

와 같은 테트로미노는 (내 구현상)확인하지 못해서,

OXO

XXX

OXO

(i,j)를 기준으로 십자가 모양의 모든칸의 합을 다 구해놓고 (동,서,남,북)칸을 빼가며 확인해줬다.

devxb/JJUNalgo

백준 알고리즘 소스코드🙃. Contribute to devxb/JJUNalgo development by creating an account on GitHub.

github.com