백준 1783번 C++ 풀이

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

1783번: 병든 나이트

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	실버 4

문제

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

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

병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

입력

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

출력

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

---

이 문제가 특이한 것은 오로지 오른쪽으로만 움직인다는 점이다. 따라서 움직임은 다음과 같다.

나이트의 움직임

우선 세로(n)가 1이라면 나이트는 움직일 수 없기 때문에 본인이 처음에 위치한 좌하단 단 한칸만을 여행한 셈이 된다. 따라서 이때는 1이다.

 

세로가 2라면, 나이트는 2, 3번의 방법으로만 움직일 수 있다. 하지만 이동 횟수가 4 이상이라면 1번과 4번의 움직임도 같이 해야 하지만, 1, 3번 방법은 세로의 길이가 3 이상이어야 하기 때문에 더 이상 움직일 수 없다. 

따라서 이러한 경우에는 가로가 아무리 길어도 최대 4칸밖에 움직일 수 없다. 하지만 이때의 가로가 7보다 작은 경우 어떻게 해야 할까? 1부터 시작하여 2, 3번의 움직임은 가로 2칸을 움직이기 때문에 (가로의 길이 + 1) / 2가 곧 칸의 개수이다. 등차수열을 배우면 당연한 이야기일 것이다.

 

그렇다면 세로가 3 이상인 경우를 보자. 이때는 1, 4번의 움직이는 방법도 사용할 수 있다. 그렇다면 m을 고려하지 않고 최대한 많은 칸을 이동하려면 어떻게 움직여야 할까? 병든 나이트는 오른쪽으로만 움직이고, m자체는 정해져 있기 때문에 오른쪽으로 덜 이동하는 1, 4번의 방법을 최대한 많이 써야 할 것이다. 하지만 4번 이상 움직이는 경우, 2, 3번 방법도 각각 한번 이상 써야하기 때문에 2, 3번 방법을 단 한번씩만 사용한 후에, 1, 4번을 계속해서 사용하면 될 것이다. 그렇기 때문에 가로로 움직이는 길이가 1씩 더 큰 2, 3번의 움직임으로 인해 총 (가로(m) - 2) 만큼의 칸을 여행할 수 있다.

 

m = 14일 때, 최대 12칸을 여행한다.

하지만 여기서도 예외가 발생한다. 1, 2, 3, 4번의 움직임을 한번씩 사용하면 총 6칸(2+2+1+1)을 가로방향으로 움직이는데, 이때 주어진 가로의 길이가 7보다 작다면 어떻게 해야 하나? 이때의 경우, 여행 가능한 칸의 최댓값은 4이다.

 

4가로의 길이가 6일 때, 여행가능한 최대 칸수는 4이다.

 

#include <bits/stdc++.h>
using namespace std;

int main () {
    // fast i/o
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // n = 세로, m = 가로
    int n, m;
    
    cin >> n >> m;
        
    if (n == 1) cout << 1;
    else if (n == 2) cout << min(4, (m + 1) / 2);
    else if (m < 7) cout << min(4, m);
    else cout << m - 2;
}