백준 No.1783 병든 나이트 - JAVA

문제

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

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

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

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

 

 

 

문제에서 키워드는 4가지 방법, 이동횟수가 4번보다 작은 경우 이동 방법에 대한 제약이 없다는 것이다. 여기서는 즉 이동횟수가 4번 이상일 경우 무조건 4가지 방법을 모두 사용해야한다는 것을 알 수 있다.

 

풀이

위로 한칸 그리고 아래로 한칸을 갈 수 있다면 2,3번 방식으로 갈 수 있고 위,아래 두 칸이 있다면 1,4번도 갈 수 있다. 즉 세로가 3 이상일 경우 4가지 방법을 다 사용할 수 있는 건데 여기서는 가로의 크기도 따라줘야 한다. 가로의 크기가 위의 4가지 방법으로 자유롭게 이동할 수 없다면 이동할 수 없기에 그렇다. 2+2+1+1을 적어도 움직여야하는데 현재 위치포함해서 적어도 7이상의 가로 크기가 있어야 4가지 방법을 다 사용할 수 있다. 세로 3 ,가로 7 4가지 방법으로 가려면 최소한 이정도 크기가 있어야 한다.

 

이제 if문을 통해 값을 걸러야 한다

 

N == 1일 경우 (세로가 1)

위 아래로 움직이지 못하므로 당연히 1이다. 현재 존재하는 칸만 있으므로 1이다

 

N == 2일 경우 

3,4번 방법으로 이동이 가능한데 3번 4번이 반복이 총 4번 이상이면 안 된다. 4번 이상일 경우 1~4번 방법을 모두 사용해야한다. 그렇기에 Math.min을 통해 값을 걸러줘야 한다. 세로가 2이면 (M+1)/2 만큼 이동할 수 있다. 

 

위에 두 가지 경우가 아니라는 것은 N은 3이상이라는 것이고 여기서 M이 7보다 작다면?

M칸(현재위치포함)만큼 이동할 수 있다.  왜냐하면 3,4번은 오른쪽으로 한칸씩 이동하기 때문이다. 

그래서 M만큼 이동하지만 4보다 크면 안됨

 

N이 3이상이고 M이 7보다 크다면 

1~4번 방식을 모두 사용해야 하는데 1,4번은 오른쪽으로 두칸씩 이동하기에 1번씩 사용하고 나머지 2,3을 모두 사용한다면 M-2번만큼 칸을 갈 수 있다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int count = 0;
        if (N == 1) {
            count = 1;
        } else if (N == 2) {
            count = Math.min(4, ((M + 1) / 2));
        } else if (M < 7) {
            count = Math.min(4, M); //2,3만 반복하면 M만큼 반복
        } else if(M >= 7){
            count = M - 2;  //1,4번방향 한번씩 움직여야하므로
        }

        System.out.println(count);

    }
}

 

 

참고

https://songwonseok.github.io/algorithm/BOJ-1783/

백준 1783: 병든 나이트(Java)