[백준] 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이 이미 2억인것 같은데

이보다 넘어가면 답이 없으거라 생각했다.

일단 가장 간단한 방법부터 생각해 봤다.

바로 n이 1일 때였다.

왜냐하면 세로가 1이기 때문에, 나이트는 움직일 수 없다.

움직일 수 없기 때문이다.

그 다음은 n이 2일 경우다.

이 부분은 조금 햇갈리는데

계산해보면

1 2 2 3 3 4 ....

가 된다.  그 다음 부터는 4가 된다고 하는데 솔직히 잘 모르겠다.

타 블로그를 참조해보면 네가지 조건을 전부 사용해야하기 때문이라고 한다.

아무튼 그럼 최댓값이 3이된다.(4를 제외하구)

그러면 이걸 어캐구하냐

우리는 세로말고 가로도 알고 있다. 가로에 2를 나눠주면 된다.

근데 나머지가 있을 수 있으니 그냥 가로+1을한뒤 2를 나눠주는 게 좋을 것 같다.

왜냐하면 어차피 같기.. 때문이다.

 

마지막은 3보다 큰 경우다.

  여기는 2가지로 다시 나눠진다. 하나는 가로가 6보다 작을 경우,

또 다른 하나는 그렇지 않을 경우..

하필 6인 이유는 아마도 나이트가 (1+2)*2가 되는 값인것 같다.

아무튼 나이트가 갈 수 있는 최대거리인것 같다.(합리적 의심)

그거의 답은 m이다. 즉, 가로의 길이와 같다는 것 같다.

하지만 이것도 4랑 비교해줘야한다.

 

마지막은 m-2를 해주면 끝이다.

import java.util.Scanner;

public class Knight {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        if (n == 1) {
            System.out.println(n);
        } else if (n == 2) {
            System.out.println(Math.min(4,(m+1)/2));
        } else {

            if (m<=6) {
                System.out.println(Math.min(4,m));
            } else {
                System.out.println(m-2);
            }
        }
    }

}

 

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	int n,m;
	cin>>n>>m;
	
	if(n==1)
	{
		cout<<1;
	}
	else if(n==2)
	{
		if(m<3)
			cout<<1;
		else if(m>=3 && m<5)
			cout<<2;
		else if(m>=5 && m<7)
			cout<<3;
		else if(m>=7)
			cout<<4;
	}
	else	//n>=3
	{
		if(m==1)
		{
			cout<<1;
		}
		if(m==2)
			cout<<2;
		if(m==3)
		{
			cout<<3;
		}
		if(m>=4 && m<=6)
		{
			cout<<4;
		}
		if(m>=7)
		{
			cout<<5+m-8+1;
		}
	}
	
	
	return 0;
}