시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 512 MB 54 19 18 52.941%

문제

게임 덕후 준서는 PC, PlayStation, XBOX 등 게임 플랫폼을 가리지 않고 모든 게임을 다 해보기로 유명하다. 그 는 최근에 Mobile App Store에서 ‘Crush Fever’란 게임을 발견했다. 그 게임은 ‘퍼○도라’로 유명한 게임의 변형 판 인데, 일반적인 파티 편성 게임과 달리 독특하게 퍼즐의 요소가 결합되어 있다. 해당 게임은 크게 유닛 육 성, 관리 부분과 던전 공략으로 나뉘어져 있다. 준서는 던전공략을 손으로 진행하다가 진행이 잘 되지 않자 화 가 나서 핸드폰을 집어 던졌다. 그리고 잠깐 물을 마시면서 화를 식히고 있던 도중에 좋은 아이디어가 떠올랐 다. “던전을 내 손과 뇌로 못 깬다면 프로그램으로 깨게 만들면 되잖아?” 하지만 준서는 매우매우매우 귀찮았 기 때문에 효과적인 퍼즐 해결 부분은 작성하고 싶어 하지 않았다. 아무리 그래도 준서는 조그마한 양심은 남 아 있었기에, 핸드폰에 연동해서 자동으로 게임을 진행하는 것은 직접 만들기로 했다. 대신 당신에게 퍼즐을 고득점으로 해결할 수 있는 프로그램 작성을 의뢰했다. 게임의 퍼즐 부분은 아래 그림과 같다.

퍼즐의 각각의 조각들은 아무렇게나 쌓여 있는데, 이 게임에서는 자신의 차례에 하나의 퍼즐조각을 세번 선택하는 것으로 공격을 진행할 수 있다. 퍼즐조각 한 개를 선택하면 해당 퍼즐에 가까이 있는 같은 종류의 퍼즐들이 연쇄적으로 부서지게 된다. 그리고나서 비어 있는 공간은 위의 퍼즐들이 아래로 떨어져서 다시 쌓이게 된다. 연쇄적으로 부서진 퍼즐의 개수를 P라고 할 때, 하나의 퍼즐을 터트릴 때의 점수 계산식은 P2과 같다. 식을 보면 알겠지만 제일 길게 연결되어 있는 퍼즐을 터트리면 그만큼의 고득점을 얻을 수 있다. 준서는 단순히 고득점 점수를 얻고 싶어하기 때문에 주어지는 퍼즐은 위처럼 복잡한 구조는 아니다. 퍼즐은 아래처럼 격자형식으로 주어진다. 

여기서 3을 지우면 아래와 같은 모습이 된다.

퍼즐의 조각 종류는 총 5가지이며, 준서의 차례에 얻을 수 있는 최고의 고득점을 구해주는 프로그램을 작성하여 준서를 도와주자.

입력

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 퍼즐의 너비 M, 높이 N이 주어진다. (1 ≤ M, N ≤ 8) 두번째 줄부터 N+1번째 줄까지 M개의 숫자 c가 주어진다. (1 ≤ c ≤ 5) 

출력

프로그램의 출력은 표준 출력으로 한다. 준서의 차례에 얻을 수 있는 최고 고득점을 출력한다.

예제 입력 1

6 3
1 1 1 1 1 1
1 1 1 2 2 2
2 2 2 3 3 3

예제 출력 1

126

힌트

출처

University > 숭실대학교 > 2017 SCCC Summer Contest D번

  • 데이터를 추가한 사람: adh0463