[99클럽 코테 스터디 10일차 TIL] 병든 나이트

 

10일차 문제

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

 

 

 

문제 풀이

규칙을 찾아야 하는 문제였다.

 

처음에는 dfs나 bfs 풀이를 생각했으나 입력값이 매우 크므로 이가 불가능하다는 것을 알았다.

구글링으로 규칙을 찾아 해결했다..

 

참고 : https://velog.io/@guswlsdl0121/백준-1783번-병든-나이트-with-Java-25bw2hsa

 

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 answer = 0;

        if(N == 1) {
            // N이 1이라면 이동 불가
            answer = 1;
        } else if(N == 2) {
            // N이 2라면 2번과 3번 움직임만 가능함
            answer = Math.min((M+1)/2, 4);
        } else {
            if(M < 7) {
                // 1~4번 모든 방식으로 움직일 수 있음
                answer = Math.min(M, 4);
            } else {
                // M이 7보다 클 경우 각 M마다 나이트를 움직일 수 있음
                answer = M - 2;
            }
        }
        System.out.println(answer);
    }