원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
양손에 V
원제: 양손에 V
문제
각 격자가 흰색 또는 검은색으로 칠해져 있는 행 열의 격자판이 주어진다.
다음과 같은 행동을 “V자 색칠하기” 라 하자:
- 흰색 격자를 하나 선택한다.
- 선택한 격자부터 시작하여 왼쪽 위 대각선을 따라 움직이면서 흰색이 아닌 격자가 나오거나 외부로 빠져나가기 전까지의 격자들을 모두 파란색으로 칠한다.
- 선택한 격자의 한 칸 오른쪽 위 격자부터 시작하여 오른쪽 위 대각선을 따라 움직이면서 흰색이 아닌 격자가 나오거나 외부로 빠져나가기 전까지의 격자들을 모두 파란색으로 칠한다.
“V자 색칠하기”를 두 번 했을 때 가능한 파란색 격자의 최대 개수를 구하여라.
예를 들어, 다음과 같은 격자판이 주어졌다 하자.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
5행 5열의 격자에서 V자 색칠하기를 한 후 격자판의 상태는 다음과 같다.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
그 후, 5행 9열의 격자에서 V자 색칠하기를 하면 다음과 같이 총 11개의 격자가 파란색으로 칠해진다.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
반면, 5행 9열의 격자에서 먼저 V자 색칠하기를 한 후 5행 5열의 격자에서 V자 색칠하기를 하면 다음과 같이 총 13개의 격자가 파란색으로 칠해진다.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
두 번의 V자 색칠하기로 13개보다 많은 격자를 파란색으로 칠하는 방법은 존재하지 않으므로, 주어진 격자판에서의 답은 13이 된다.
제약 조건
- 주어지는 격자판에서 흰색 격자는 최소 2개 존재한다.
부분문제
- (11점)
- (20점)
- (24점)
- (45점) 추가 제약 조건 없음.
입력 형식
첫 번째 줄에 과 이 공백으로 구분되어 주어진다.
두 번째 줄부터 개의 줄에 걸쳐 격자판에 대한 정보가 주어진다. 각 줄에는 또는 로 이루어진 길이 인 문자열이 주어진다. 개의 줄 중 번째 줄의 번째 문자가 이면 격자판에서 행 열의 격자가 흰색, 이면 검은색임을 뜻한다. ()
출력 형식
첫 번째 줄에 가능한 파란색 격자의 최대 개수를 출력한다.
예제
예제 1
5 11 10001000000 01000100000 00100110001 00010101010 00001000100
13
예제 2
3 3 111 111 111
6