백준(BOJ) 1783번 병든 나이트

문제 : https://www.acmicpc.net/problem/1783

문제

병든 나이트가 N * M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

병든 나이트는 병들었지만, 그래도 명색이 체스 나이트이기 때문에 많은 칸을 방문하고 싶어 한다. 병든 나이트의 이동에는 제약이 있다. 만약, 이동 횟수가 4번 이상인 경우에는 위의 이동 방법을 각각 한 번 이상 이용해야 한다.

체스판의 크기가 주어졌을 때, 병든 나이트가 방문할 수 있는 칸의 최대 개수를 출력하는 프로그램을 작성하시오. 처음에 있는 칸도 센다.

풀이 :

세로가 1이거나 2이거나 아니면 3보다 크거나 같은 경우로 나누어서 생각 하자.

세로가 1칸이라면 어느 방향으로도 이동할 수 없으니 1칸이다.

세로가 2칸이라면 2,3 번을 통하여 (M-1)/2 칸 + 1 (처음위치) 만큼 돌아다닐 수 있지만  이동 횟수가 4번 이상인 경우에는 위의 이동 방법을 

각각 한 번 이상 이용해야 한다. 라는 조건에 의하여 최대 3 + 1칸밖에 될 수 없다.

세로가 3칸이라면 가로가 7칸 이상인 경우는 1,2,3,4를 모두 만족시킬 만한 가로칸이 7칸은 되어야 하므로 (1+2+2+1), 2,3을 한번씩 써주고 나머지는 1과 4로 채우면 최대의 칸을 구할 수 있다.

만약 가로가 7칸 미만이라면 1과 4를 통해 ( M-1 )+ 1만큼 채울 수 있지만 이동 방법 조건에 의하여 역시 최대 3 + 1칸 밖에 될 수 없다.

코드 ( C++ )

#include <iostream>

#include <algorithm>

using namespace std;

int N, M;

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(0);

cin >> N >> M;

if (N == 1)

cout << 1 << "\n";

else if (N == 2)

cout << min(4,(M-1)/2 + 1) << "\n";

else

{

if (M >= 7)

cout << M - 2 << "\n";

else

cout << min(4, M) << "\n";

}

return 0;

}