백준 1783번 병든 나이트

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

1783번: 병든 나이트

 

문제

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

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

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

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

 

입력

첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.

 

출력

병든 나이트가 방문할 수 있는 칸의 개수중 최댓값을 출력한다.

 

풀이

이 문제를 해결하기 위한 중요 포인트를 골라보았다.

• 어떻게 움직이든 적어도 1칸 이상은 오른쪽으로 움직여야한다.
• 위, 아래 번갈아가며 움직이면 세로 3칸 이내로 움직임을 제한할 수 있다.
• 이동 횟수가 4번 이상인 경우 반드시 6칸 오른쪽으로 이동했어야한다.
• 4가지 움직임을 다 하였으면 같은 움직임을 계속해도 상관없다.
• 이동 횟수가 4번 미만인 경우 같은 움직임을 또 해도 상관없다.

따라서, 세로 길이 N이 3이상이고, 가로 길이 M이 7이상이면

[6칸 오른쪽으로 움직인 후 남은 가로 길이 = 나이트가 방문할 수 있는 칸의 최대 개수] 가 성립한다.

그렇다면, N이 1,2일 때와 M이 7미만일 경우 예외처리 사례를 보자.

 

i) N = 1

위로 갈 수 없으므로, 방문 칸수는 처음 그대로 1이다.

 

ii) N = 2

이 경우, 위아래 이동범위는 1이므로, 반드시 오른쪽으로 2칸씩 이동하면서 움직여야하는데

조건에서 4번 이상 이동할 경우 반드시 위 또는 아래쪽으로 2칸 움직여야하므로 가로가 아무리 길어도 이동횟수는 3이다. 따라서 방문 칸수는 최대 4까지 가능하다.

 

N의 예외처리를 다 하였으므로 이제 N을 고려하지 않은 M의 예외 케이스를 살펴보자.

iii) M = 2

• 1칸 이동가능하다.

iv) M = 3

• 두 칸 이동 가능하다.

 

v) M = 4,5,6

아래부터 M = 4, 5, 6이다.

• M = 4~6일 경우 모두 4가지 이동을 할 수 없기때문에 모두 3칸 이동까지만 가능하다.

소스코드

#include <iostream>
using namespace std;
 
int main()
{
    int n, m; scanf("%d%d", &n, &m);
    if (m == 1 || n == 1) printf("%d", 1); //둘 중 하나만 1이어도 이동x
    else if (n == 2) {
        if (m == 2) printf("%d", 1);
        else if (m == 3 || m == 4) printf("%d", 2);
        else if (m == 5 || m == 6) printf("%d", 3);
        else printf("%d", 4);
    }
    else { //n이 3 이상이면 n은 고려하지 않아도 된다.
        if (m == 2) printf("%d", 2);
        else if (m == 3) printf("%d", 3);
        else if (m == 4 || m == 5 || m == 6) printf("%d", 4);
        else { //4가지 다 움직일 수 있을 때
            printf("%d", m - 2);
        }
    }
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~