개발자 크루

HSAT_LIST

다풀고 시험치자

HSAT_LIST

썸네일

[HSAT 2회 정기 코딩 인증평가 기출] Garage game

난이도
3 단계
참가자
0
제출
0
정답률
0.00 %
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
JavaScript 2초 256MB
C 1초 256MB
C++ 1초 256MB
Java 2초 256MB
Python 2초 256MB

자율주행 기술의 발전과 함께 차량 내 인포테인먼트 기술 또한 많은 주목을 받고 있다. 최근 자동차 실내에는 디스플레이의 대형화를 비롯해 새로운 제어 기술이 빠르게 적용되고 있는데, 완전 자율주행 시대가 다가올 수록 이런 변화가 가속화될 전망이다.

개인 맞춤형 인포테인먼트 시스템 역시 핵심 기능 중 하나다. 자율주행 시대에 발맞춰 차량 내 디지털 시스템을 활용한 게임을 개발하고 있다.




게임의 룰은 가로 세로 N칸의 차고(격자)가 있고, 각 차고에는 색깔이 있는 자동차가 하나씩 있다. 한 턴에 한 칸을 선택하며, 선택한 칸과 상하좌우 칸에 들어있는 자동차의 색이 같다면 모두 사라진다. 그리고 사라진 칸들과 연결된 칸들의 상하좌우 칸에 들어있는 자동차의 색이 같다면 함께 사라진다. (문제 하단 예시 참고.)


이때, 획득할 수 있는 점수는 사라진 자동차의 개수와 사라지는 차고 칸을 모두 포함하는 가장 작은 직사각형의 넓이의 합이다.

자동차들이 사라지고 나면 위에 있는 자동차들이 아래로 떨어져 빈 칸을 채운다. 위쪽에는 충분한 자동차들이 더 있어서 위에서 추가적으로 떨어지며 모든 칸을 채운다.


위에서 어떤 자동차들이 떨어질지는 입력으로 주어진다. 위와 같은 게임을 3차례 반복 했을 때, 주어진 조건에서 얻을 수 있는 가장 큰 점수를 계산하라.

제약조건

1 ≤ N ≤ 15

색상 번호는 1 이상 109이하의 자연수이다.

입력형식

입력으로는 차고 격자 칸의 가로, 세로 길이인 N이 첫 줄에 주어진다.

다음 3N개의 줄에 N개의 자연수가 주어진다.

각 자연수는 차고 칸에 있는 자동차의 색상 번호이다.

출력형식

주어진 조건에서 게임을 3차례 시뮬레이션 했을 때 얻을 수 있는 가장 큰 점수를 출력한다.

입력예제1

2 1 1 2 2 1 1 3 3 4 4 1 2

출력예제1

15

입력예제2

3 8 5 1 9 6 1 10 7 1 11 1 3 12 1 3 13 1 3 1 2 2 1 2 2 1 2 2

출력예제2

36