[BOJ][Java] 백준 1783번: 병든 나이트

문제 설명

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

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

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

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

 

문제 풀이

이 문제의 핵심은 오른쪽으로만 이동하는 것과 이동 횟수가 4이상일 경우 모든 조건을 한 번씩 사용해야한다 입니다. 

세로가 1일 때 체스는 아무 곳으로도 이동할 수 없어 답은 1입니다.

세로가 2일 때 체스는 2,3번 조건 밖에 활용할 수 밖에 없고 가로가 7이상이 될 경우 횟수가 4번이상이 되기 때문에 모든 조건을 사용할 수 없어 Math.min(4, (M+1)/2)입니다.

가로가 7미만일 때 Math.min(4, M)이며 7이상일 땐 M-2입니다.  (아래 표에 설명을 체크해놨습니다)

 

<M=3> => 3칸

시작		1
	4

<M=4> 이동횟수가 4미만이기 때문에 4, 1, 4조건이 가능합니다. => 4칸

시작		1
	4		4

<M=6>가로 5번째 줄에 도달할 경우 더이상 이동할 수 없습니다. => 4칸

시작		1
				3
	4

<M=7> 7번째 줄에서 모든 조건을 한 번씩 사용하는 것이 확인됩니다. => 5칸

시작		1				2
				3
	4

<M=9> 7칸

시작		1				2		1
				3
	4						4

 

풀이 코드

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int N, M;

    private static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
    }

    static int process(){
        if(N == 1) return 1;
        if(N == 2) return Math.min(4, (M+1)/2);
        if(M<7) return Math.min(4, M);
        return M-2;
    }

    public static void main(String[] args) throws IOException {
        input();
        System.out.println(process());
    }
}

 

<출처>

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

1783번: 병든 나이트