시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 14 7 5 45.455%

문제

초보 게임개발자 동이는 프로그래밍을 공부하며 자신만의 테트리스 게임을 개발하고 있다. 테트리스는 이미 세계적으로 유명한 게임으로, 20행 10열의 그리드 게임판에서 위에서부터 추락하는 블록 도형을 회전시키거나 좌우로 위치를 옮겨가며 쌓아 올리는 게임이다. 게임을 진행하는 중에 블록이 아래위로 충돌하여 멈추게 되면 블록으로 가득 찬 행은 삭제되고 삭제된 한 줄마다 사용자는 1점을 얻는다. 이때 그 행 위의 행들은 모양을 유지한 채로 내려온다. 블록 도형은 총 7가지 종류가 있으며 사용자는 각각 90, 180, 270도로 회전시켜 사용할 수도 있다.

<20행 10열의 게임판 예시(좌)와 일곱가지 테트리스 블록 도형(우)>

테트리스 게임의 규칙은 비교적 단순하므로 동이는 생각보다 이른 시간 안에 게임을 완성할 수 있었다. 동이는 자신이 만든 테트리스 게임을 손수 플레이하며 테스트하려고 한다. 다만 동이는 평소 손이 느리기로 유명해서 어느 정도 이상의 난이도는 도저히 스스로 클리어할 수가 없었다. 그래서 동이는 자신만을 위해서 아래와 같은 치트 기능을 개발하기로 했다.

  • 현재 동이가 조작하던 블록 도형은 제거된다.
  • 다음번 등장하는 블록 도형은 동이가 조작할 수 없으며, 자동으로 최적의 위치에 등장하여 최적의 경로로 이동한다.
  • 다음번 등장하는 블록은 7가지 도형 중 위와 같이 움직여서 가장 많은 줄을 제거할 수 있는 도형과 방향이 자동으로 선택된다.
  • 다만 이동하는 과정에서 도형은 처음 등장한 모양에서 변경되거나 회전하지 않는다. 이를 고려하여 최적의 도형이 등장한다.

예를 들어서 위의 예시로 주어진 게임판에서 치트 기능을 사용하면 4행 1열짜리 길쭉한 블록 도형이 오른쪽 끝 칸에 등장해 자동으로 수직으로 하강한다. 이때 플레이어는 두 줄을 제거하고 2점을 얻을 수 있다. 다른 도형으로 두 줄 넘게 제거하는 것이 불가능하다.

현재 플레이어의 게임판 정보가 주어질 때 치트 기능을 사용하면 최대 몇 줄을 제거할 수 있을지 계산하는 프로그램을 작성하시오. 단, 현재 가장 위의 네 줄은 항상 모두 비어있음이 보장된다.

입력

총 20줄에 걸쳐서 게임판의 각 줄의 상태를 나타내는 문자열이 0과 1로 구성되어 주어진다. 각 줄은 10글자이며, 0은 비어있는 칸을 나타내고 1은 블록이 채워져 있는 칸을 나타낸다.

먼저(위에) 입력 된 문자열이 게임판의 위쪽 줄을 나타낸다. 위에서 1~4번째 줄에는 항상 0으로 채워져 있음이 보장된다.

각 행마다 적어도 한 칸이 비어있음이 보장된다.

출력

인공지능 기능으로 제거할 수 있는 최대 줄의 수를 한 줄에 출력한다.

예제 입력 1

0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
1111111110
1111110110
1111111110
1111101110
1111111110
1111011110
1111101110
1111111110
1111111110

예제 출력 1

2

예제 입력 2

0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000011
0000000001
0000000001
0000000001
0000000001
1111111101
1111111101
1111111101
1111111101
1111111101
1111111101
1111111101
1111111101
1111111101

예제 출력 2

4

힌트

예제 1: 문제 설명에 등장한 예시와 같다. 긴 막대를 오른쪽 끝 줄에 배치하여 수직으로 하강시키면 두 줄을 제거할 수 있다.

예제 2: 긴 막대를 세운 모양으로 왼쪽 끝 줄에서 하강하다가 모서리를 지나쳐 우측으로 이동시킨 후 다시 하강시키면 4줄을 제거할 수 있다.

채점

  • 예제는 채점하지 않는다.