[백준/BOJ] 1783. 병든 나이트 [Silver 4]

1783. 병든 나이트

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

code

#include <stdio.h>
int main()
{
    int n, m, cnt;
    scanf("%d %d", &n, &m);
    if (n == 1)
        cnt = 1;
    else if (n == 2)
    {
        cnt = (m + 1) / 2;
        if (cnt > 4)
            cnt = 4;
    }
    else if (m < 7)
    {
        cnt = m;
        if (cnt > 4)
            cnt = 4;
    }
    else
        cnt = m - 2;
    printf("%d", cnt);
    return 0;
}

코드는 정말 간단하다.
나이트가 갈수있는 방향 4가지의 공통점은 나이트는 오른쪽으로만 간다는것이다.
오른쪽 방향으로만 가는데 공간을 가장 잘 활용하면서 갈 수 있는 방법은 1번과 4번을 반복하는것이다.

하지만 1번과 4번을 반복하기 위해서는 세로의 길이 N이 3이상이여야 한다.

그래서 N이 1인경우와 2인경우, 3인경우를 나눠서 생각을 해야한다.
세로가 1이면 일단 움직일수도없기때문에 cnt는 1로 고정이다.

세로가 2이면 2번조건3번조건을 반복해서 갈순 있지만, 4번이상 움직이려면 1,2,3,4조건을 모두 써야하기 때문에, 4번이상 움직이지 못하기 때문에 cnt = (m+1)/2인데, 4이상이면 4로 고정된다.

세로가 3이상이면, 이제 가로 길이에 신경을 써야하는데,
1,2,3,4조건을 모두 지나가면 적어도 가로길이가 7, 칸은 5개가 되어야 하는데,
세로가 3이상이고, 가로길이가 7이하일때는 cnt는 가로길이와 같다. 그러나 4번이상 움직이지 못하기 때문에 cnt가 4이상이면 4로 고정된다.

세로가 3이상이고, 가로길이가 7이상일때는 가로길이 m에서 -7(가로길이)를 빼주고 +5(방문한 칸의 갯수)를 더해줘야 한다.