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

문제링크 : https://www.acmicpc.net/problem/1783

문제

문제를 해결한 방법

입력값이 엄청나게 크기 때문에 BFS로 접근하면 시간초과납니다…

저는 처음에 문제를 보고 종이에 몇가지 케이스를 그려보니 규칙이 보였습니다.

1) N이 1인 경우

​

• 아무방향으로도 움직일 수 없어서 count는 1

2) N이 2인 경우

• 2,3번 방향으로만 움직일 수 있어서 count는 (M+1)/2
• 네방향 다 움직일 수 없어서 총 3번까지만 움직임(max = 4, 시작지점 포함)

3) N이 3 이상일 경우

​

• M < 7

• 1,4번 방향을 번갈아가며 움직이면 count는 M

• 네방향 다 움직일 수 없어서 총 3번까지만 움직임(max=4)

  

• M >= 7

• M이 7일 때 네방향 모두 움직일 수 있음
• 그 이후에는 1,4번 방향을 번갈아가며 움직이면 count는 M-2

소스 코드

package baek;

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

public class Main_1783_병든나이트 {
	
/*
	1) 2칸 위로, 1칸 오른쪽
	2) 1칸 위로, 2칸 오른쪽
	3) 1칸 아래로, 2칸 오른쪽
	4) 2칸 아래로, 1칸 오른쪽
*/
    public static void main(String[] args) throws Exception{
        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 result = 0;
        
        if(N == 1) {
            // N이 1이면 이동 불가 (시작지점만)
            result = 1;
		}else if(N == 2) {
            // N이 2일 떈, 2번,3번 방향으로만 움직일 수 있음
            // 절대 4방향 다 움직일 수 없어서 최댓값은 4
            result = Math.min((M+1)/2, 4);
		}
        else if(N>=3){
            // M=7 부터 4방향 다 이동 가능
            // 4방향 다 이동한 후에는 y값이 1씩 증가하는 1번,4번 이동을 반복
            // 즉, M-2개의 칸을 갈 수 있음
			if(M < 7) {
				result = Math.min(M, 4);
			}else {
				result = M-2;
			}
		}
		
		System.out.println(result);
	}
}