[BOJ] 병든 나이트_1783 C++ 풀이

문제

N x M 크기의 체스판에서 병든 나이트는 가장 왼쪽 아래 칸에 위치해 있고 다음과 같은 4가지 방식으로만 이동할 수 있다.

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

세로 길이 N, 가로길이 M이 주어졌을때 병든 나이트가 방문할 수 있는 최대 칸수를 구하여라. 단 방문한 칸이 5개 이상이면 위의 1~4 이동 방법을 모두 한 번씩 사용해야 한다.

접근 방법

이 문제의 포인트는 결국엔 병든 나이트가 오른쪽으로 이동할 수 밖에 없다는 것이다.

즉 병든 나이트가 최대로 많은 칸을 방문할 수 있는 방법은 위아래로 번갈아 이동하며 가능한 오른쪽으로 1칸씩 만 이동하는 방법인 1,4 번 방법으로 이동하여야 한다.

단, 1,4방법은 2칸 위,아래로 움직여야한다는 조건이 있기 때문에 세로길이 N이 N<3인 경우 불가능 하다.

따라서 N==1인 경우, N==2인 경우, N>=3인 경우로 나누어 접근하였다.

먼저 N==1 인 경우 위, 아래로 이동하는 것이 아예 불가능 하므로 이동 자체가 불가능하다. 즉 최대 방문 칸수는 1이다.

N==2인 경우 2,3 방법으로 밖에 이동할 수 없다. 단 방문한 칸이 5개 이상이면 1,4 방법도 사용해야 하는 조건이 붙기 때문에 N==2인 경우 가능한 최대 방문 칸수는 가로 길이와 상관 없이 4이다.

N>=3인 경우 더이상 세로 길이에 의한 이동 방법의 제한은 없다. 가로길이 M==7 인경우 부터 1~4번 방법을 전부 한번씩 사용할 수 있으며 1~4방법을 전부 이용하여 방문한 칸의 수는 5이다. 따라서 M>=7인 경우, 5칸 이후 부터는 1,4방법으로 오른쪽으로 한칸씩 이동하기 때문에 M-2로 최대 칸수를 구할 수 있다.

구현

#include<iostream>
#include<algorithm>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int m, n; // 가로 세로
    cin>>n>>m;

    if(n==1) cout<<1;
    else if(n==2) cout<<min(4, (m+1)/2); // 세로 n=2이면 2,3 만 가능. 즉 방문한 칸이 최대 4
    else
    {
        if(m<7) cout<<min(4,m); //최대 4칸
        else cout<<m-2;
    }
    return 0;
}

BOJ_병든 나이트