백준 1783 - 병든 나이트

문제

 

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

1783번: 병든 나이트

 

 

풀이

 

높이에 따라 세 가지 경우로 나누어서 풀어야 한다.

1. 높이가 1인 경우 나이트는 이동할 수 없다.

2. 높이가 2인 경우 위로1칸 오른쪽 2칸, 밑으로 1칸 오른쪽 2칸 으로만 이동할 수 있다.

3. 높이가 3 이상인 경우 가로 길이가 7을 기준으로 나누면 된다.

 

높이가 2인 경우 이동가능한 방법으로 이동할 수 있는 최대 이동 횟수는 3번이다. 이동 횟수 4번 부터는 4가지 이동 방법을 모두 사용해야 하므로 3번까지만 이동할 수 있다. 

 

높이가 3이상인 경우 가로로 최대한 많이 이동해야 한다. 따라서 위로 2칸 오른쪽 1칸, 아래로 2칸 오른쪽 1칸의 방법을 이용해서 이동하면 된다. 4가지 이동 방법을 이용해서 이동하면 가로로 7만큼 이동하게 된다. 따라서 가로 길이 7을 기준으로 나뉘게 된다. 

위로 2칸 오른쪽으로 1칸, 아래로 2칸 오른쪽으로 1칸 방법으로 이동하게 되면 가로의 길이만큼 움직일 수 있다. 이때 가로 길이가 7이상인 경우 4가지 방법을 다 사용해야 한다. 이 때 오른쪽으로 2칸 위로 1칸, 오른쪽으로 2칸 아래로 1칸의 방법을 이용하면 중간에 1칸씩 방문을 할 수 없기 때문에 (가로 길이 - 2) 만큼 방문이 가능하다.

 

 

코드

 

#include <iostream>
 
using namespace std;
 
int N, M;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N >> M;
 
    if (N == 1) cout << 1;
    else if (N == 2) cout << min(4, (M+1)/2);
    else
    {
        if (M >= 7) cout << max(4, M-2);
        else cout << min(4, M);
    }
 
    return 0;
}