백준 1783번 : 병든 나이트

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

1783번: 병든 나이트

문제

병든 나이트가 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과 m의 크기가 20억일 떄 느낌이 왔다. 그리고 조건중에서 위아래 이동은 자유로운 편인데 오른쪽왼쪽은 무조건 오른쪽만 가는 시점에서 조건만 찾으면 생각보다 구현은 쉽겠다고 생각이 들었다.

 

그리고 이 문제를 풀 떄 조건은 

첫번쨰, 세로 n>=3 이거나 n<3으로 나누었다. (이유는 n이 3을 기준으로 위아래 2칸이동이 가능하고 불가능이 정해진다.)

두번쨰, n>=3이상이고 m>6과 m<=6을 나눈다. 이유는 위아래 이동은 자유롭고 가로만 생각하면 된다. 하지만 조건 횟수가 4를 초과하면 모두다 사용해야하는 조건이 있다. 이때 4가지방법을 다사용하면 가로는 6칸이동이 가능하다.

1)m>6일 떄는 4가지 방법 다 쓰고 오른쪽으로 한칸씩이동하면 되기 떄문에 m-2횟수이다.

2)m<=6 일 떄는 4가지 방법을 한번씩 다 못쓴다.그래서 횟수m이 정답이고 5와 6은 최솟값인 4를 출력한다.

세번쨰. n<3일 때 위아래는 제약이 있고 오른쪽은 2칸씩 밖에 안되므로 4가지 방법을 넘을 수 있는 7을 기준으로 나눈다

1)m>=7일 때 최솟값인 4출력

2)m<7일 때는 2칸씩이동이므로 (m+1)/2 출력 (1을 더하는 이유는 시작점이 1로시작하기 때문이다.)

네번쨰. n==1일 때 항상 1출력 (이동불가능)

 

코드를 보자

#include <iostream>
using namespace std;
int main(){
    int n,m;
    cin >>n >>m;
    if(n>=3&&m>6){              //세로가 3이상이면 위아래는 자유롭게 이동가능 가로가 6보다 크면 4가지 방법 다사용가능
        cout<<m-2;
    }
    else if(n>=3&&m<=6){       //가로가 6보다 작을때 
        if(m>=5){               //5이상은 항상 4가 나와야함 4가 최소
            cout<<4;
        }
        else if(m<5){         //5보다 작을때는 가로 길이만큼 가능 
            cout <<m;
        }
    }
    else if(n<3){         //세로가 3보다 작으면 위아래 이동이 1칸씩으로 제약됨 이때 오른쪽은 항상 2칸씩이동
        if(n==1){
            cout << 1;
        }
        else if(m>=7){
            cout << 4;
        }
        else if(m<7){
            cout << (m+1)/2;
        }
    }
}