루미 알고리즘

#1101플래티넘양손에 V양손에 V

KOI 2024 2차코딩초등부 4번출제 조승현이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

양손에 V

원제: 양손에 V

문제

각 격자가 흰색 또는 검은색으로 칠해져 있는 NN행 MM열의 격자판이 주어진다.

다음과 같은 행동을 “V자 색칠하기” 라 하자:

  1. 흰색 격자를 하나 선택한다.
  2. 선택한 격자부터 시작하여 왼쪽 위 대각선을 따라 움직이면서 흰색이 아닌 격자가 나오거나 외부로 빠져나가기 전까지의 격자들을 모두 파란색으로 칠한다.
  3. 선택한 격자의 한 칸 오른쪽 위 격자부터 시작하여 오른쪽 위 대각선을 따라 움직이면서 흰색이 아닌 격자가 나오거나 외부로 빠져나가기 전까지의 격자들을 모두 파란색으로 칠한다.

“V자 색칠하기”를 두 번 했을 때 가능한 파란색 격자의 최대 개수를 구하여라.

예를 들어, 다음과 같은 격자판이 주어졌다 하자.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

5행 5열의 격자에서 V자 색칠하기를 한 후 격자판의 상태는 다음과 같다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

그 후, 5행 9열의 격자에서 V자 색칠하기를 하면 다음과 같이 총 11개의 격자가 파란색으로 칠해진다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

반면, 5행 9열의 격자에서 먼저 V자 색칠하기를 한 후 5행 5열의 격자에서 V자 색칠하기를 하면 다음과 같이 총 13개의 격자가 파란색으로 칠해진다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

두 번의 V자 색칠하기로 13개보다 많은 격자를 파란색으로 칠하는 방법은 존재하지 않으므로, 주어진 격자판에서의 답은 13이 된다.

제약 조건

  • 1≤N,M≤3 0001 \le N, M \le 3\,000
  • 주어지는 격자판에서 흰색 격자는 최소 2개 존재한다.

부분문제

  1. (11점) N,M≤20N, M \le 20
  2. (20점) N,M≤100N, M \le 100
  3. (24점) N,M≤500N, M \le 500
  4. (45점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 NN과 MM이 공백으로 구분되어 주어진다.

두 번째 줄부터 NN개의 줄에 걸쳐 격자판에 대한 정보가 주어진다. 각 줄에는 00 또는 11로 이루어진 길이 MM인 문자열이 주어진다. NN개의 줄 중 ii번째 줄의 jj번째 문자가 11이면 격자판에서 ii행 jj열의 격자가 흰색, 00이면 검은색임을 뜻한다. (1≤i≤N,1≤j≤M1 \le i \le N, 1 \le j \le M)

출력 형식

첫 번째 줄에 가능한 파란색 격자의 최대 개수를 출력한다.

예제

예제 1

입력
5 11
10001000000
01000100000
00100110001
00010101010
00001000100
출력
13

예제 2

입력
3 3
111
111
111
출력
6

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2024년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.