연습문제

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

난이도
Lv. 3
제출
1,659 명
참가자
332 명
정답률
10.16 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
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




첫번째 예제를 보면, 시뮬레이션 1회차에 4번 색상의 차량을 가지고 있는 차고(격자)가 2곳이 있다. 사라지는 자동차의 개수(2점)와 해당 차고를 포함하는 가장 작은 직사각형 면적(2점)을 합한 4점을 획득한다.


시뮬레이션 2회차에서 3번 색상의 차량을 가지고 있는 차고가 2곳이 있다. 사라지는 자동차의 개수(2점)와 해당 차고를 포함하는 가장 작은 직사각형 면적(2점)을 합한 4점을 획득하여 총 8점 획득한다.


마지막으로, 시뮬레이션 3회차에서 1번 색상의 차량을 가지고 있는 차고가 3곳이 있다. 사라지는 자동차의 개수(3점)와 해당 차고를 포함하는 가장 작은 직사각형 면적(4점)을 합한 7점을 획득하여, 총 15점을 획득한다.




두번째 예제를 보면, 시뮬레이션 1회차에 2번 색상의 차량을 가지고 있는 차고가 6곳이 있다. 사라지는 자동차의 개수(6점)와 해당 차고를 포함하는 가장 작은 직사각형 면적(6점)을 합한 12점을 획득한다.


시뮬레이션 2회차에서 3번 색상의 차량을 가지고 있는 차고가 3곳이 있다. 사라지는 자동차의 개수(3점)와 해당 차고를 포함하는 가장 작은 직사각형의 면적(3점)을 합한 6점을 획득하여 총 18점 획득한다.


마지막으로, 시뮬레이션 3회차에서 1번 색상의 차량을 가지고 있는 차고가 9곳이 있다. 사라지는 자동차의 개수(9점)와 해당 차고를 포함하는 가장 작은 직사각형의 면적(9점)를 합한 18점을 획득하여, 총 36점을 획득한다.


만약 아래와 같이 시뮬레이션 2회차에서 1번 색상의 차량을 선택하는 경우, 사라지는 자동차의 개수(6점)와 해당 차고를 포함하는 가장 작은 직사각형의 면적(6점)을 합한 12점을 획득할 수 있으나, 시뮬레이션 3회차에서 사라지는 자동차의 개수(3점)과 해당 차고를 포함하는 가장 작은 직사각형의 면적(3점)으로 6점을 획득하여 총 30점을 획득하여 가장 큰 점수가 될 수 없다.


목록