[백준] 1783 : 병든 나이트 JAVA 풀이

 

 

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

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

이 포스트를 참고해서 풀었다.

 

이동 횟수가 4 이상이라면 모든 방향으로 한번씩은 이동해야 한다는 게 무슨 뜻인지 잘 이해가 되지 않았는데,

이 포스트처럼 따라그려보니 이해가 됐다.

 

 

 

1. N M을 입력받음

 

2. 최대 개수를 세는 변수 cnt를 생성함

 

3. N이 1인 경우는 어디로도 움직일 수 없으므로 최대 개수는 1이 됨

 

4. N이 2인 경우는 2, 3 방향으로만 움직일 수 있으므로,

    최대 개수가 시작지점을 포함해 4를 넘을 수가 없음

    2, 3 방향으로 번갈아서 움직이면 (M+1)/2가 됨

    (M+1)/2과 4 중 더 작은 값으로 cnt를 갱신함

 

5. N이 3인 경우는 1, 2, 3, 4 네 방향 모두로 움직일 수 있는 경우와 그렇지 않은 경우로 나뉨

    네 방향 모두 오른쪽으로 이동하기 때문에 M의 크기에 따라 두 경우로 나뉘게 됨

    5-1. M<7이라 1, 2, 3, 4 모든 방향으로 움직일 수 없는 경우

           최대 개수는 1, 4를 반복해 오른쪽으로 한 칸씩 이동해서 M이 되거나,

           네 방향으로 이동할 수 없으니 4가 됨

           M과 4 중 더 작은 값으로 cnt를 갱신함

    5-2. M>=7이라 1, 2, 3, 4 모든 방향으로 움직일 수 있는 경우

           네 방향으로 한 번씩 이동하면 오른쪽으로 +1 +2 +2 +1로 이동하게 됨

           그 이후로는 1, 4를 반복하며 오른쪽으로 한 칸씩 이동할 때가 최대 개수가 되므로 M-2가 됨

 

import java.io.*;
import java.util.*;
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 max = 0;
        
        if(N==1){
            max = 1;
        }
        else if(N==2){
            max = Math.min((M+1)/2, 4);
        }
        else if(N>=3){
            if(M<7){
                max = Math.min(M,4);
            }
            else{
                max = M-2;
            }
        }
        
        System.out.println(max);
    }
}