[BOJ 27512 // C++] 스네이크

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 27512번 문제인 스네이크이다.
문제는 아래 링크를 확인하자.

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

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;
}