백준 1783 병든 나이트

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

public class Sick_Knight {
    static int N,M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int count = 1;
        if(N<3){
            if(N==1) {
                System.out.println(count);
                return;
            }
            count = 1+(M-1)/2;
            if(count>4){
                count = 4;
            }
        }
        else {
            if(M<7){
                count = M;
                if(count>4){
                    count = 4;
                }
            }
            else {
                count = 1+4+M-6-1;
            }
        }
        System.out.println(count);
    }
}

풀이방법

이 문제를 풀때는 N<3보다 작아서 1,2,3,4번 방법을 모두 사용하는것은 불가능 할때를 기준으로 놓고 푼다.

1. N이 3보다 작을때, 3보다 크거나 같을때를 기준으로 나누고, N이 1일때는 아예 움직일 수 없으므로 첫째칸 1칸만 탐색할 수 있다.
2. N이 2일때는 첫째칸 + M-1/2(2,3번방법으로 가로로 2칸씩 탐색) 이되며, 4가 넘어가면 안된다.(1,2,3,4 다써야해서)
3. N이 3보다 크거나 같을때는 1,2,3,4번을 다쓸 수 있냐 못쓰냐를 기준으로 나눈다 (M<7일때)
4. M<7일때는 1,2,3,4번을 다 사용할 수 없으므로 4칸까지만 탐색할 수 있고, 1,4번 방법만 사용하므로 현재칸 + M-1 (1,4번 방법으로 가로로 1칸씩)이 된다.
5. M>=7일때는 1,2,3,4번을 한번씩 사용후, 1,4번만 계속 반복하는것이 최대칸 탐색방법이 된다.
   현재칸+4(1,2,3,4번한번씩 탐색한 칸)+M-6-1(1,2,3,4번 탐색한 칸 제외 후 가로로 1칸씩)

후기

처음에 dfs로 5칸이 되면 다른 dfs를 들어가도록 설계하였는데, 일단 하면서도 모순이 많았고 애초에 입력값이 너무커서 dfs설계를 하면 안되는 문제 였다.
이 문제는 N이 1일때부터 차례로 하나씩 직접 그려보면서 풀어서 규칙을 찾아야하는 문제였다.