[BOJ 27512 // C++]

※ 작성자가 취미로 프로그래밍을 배우고 있는 사람이라 정확하지 않은 정보가 포함되어 있을 수 있습니다 ※

이번에 살펴볼 문제는 백준의 문제 #27512 뱀이다.
문제는 아래 링크를 확인해주세요.

https://www.acmicpc.net/problem/27512

주어진 그리드가 바둑판처럼 칠해지면 뱀이 검은색과 흰색 사각형 사이를 번갈아 나타납니다. 따라서 문제의 “최선의 전략”을 유지하려면 대기열의 길이가 일정해야 합니다.

다음은 문제에 대한 답이 주어진 보드의 셀 수를 초과하지 않는 가장 큰 짝수임을 증명하는 과정을 설명합니다.

(1) 셀 수가 짝수일 때, 적어도 한 변의 셀 수는 2K이다. 예를 들어 이 쪽을 K로 반으로 분할하여 타일을 나누면 각 타일의 모든 사각형을 통과하는 방법을 쉽게 찾을 수 있습니다. 이 개별 플레이트가 원래 부착된 면을 조작함으로써 이제 이러한 경로를 병합하고 하나의 그랜드 사이클로 변환할 수 있습니다. 특정 경로를 찾는 것은 어렵지 않으므로 스스로 생각하십시오.

(2) 사각형의 개수가 홀수인 경우 먼저 제거된 타일의 정점에 사각형이 있는 타일을 고려합니다. 제거된 셀과 “나머지 보드”가 있는 열을 별도로 고려하십시오. “나머지 보드”의 열 수가 짝수이므로 위 1.에서 설명한 방법을 사용하여 경로를 찾을 수 있습니다. 이전 문장에서 괄호 안에 포함된 속성을 사용하여 제거된 행의 사각형을 “남은 보드” 주기로 가져오는 방법이 있습니다. 구체적인 방법을 찾는 것은 어렵지 않으니 그것도 생각해보자.

아래는 제출된 소스코드입니다.

#include <iostream>
using namespace std;

int N, M;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	if ((N * M) & 1) cout << N * M - 1;
	else cout << N * M;
}