[백준 1783번] 병든 나이트 (Java 풀이)

백준알고리즘 1783번 : 병든 나이트

 

 

처음 보았을 때 조금 까다롭게 느껴졌는데, 규칙을 찬찬히 쪼개면서 생각해보니 어렵지 않게 풀렸다.

 

드물게 switch~case문을 사용하기에 적합한 문제였던 것으로 보인다.

 

 

 

풀이 과정

---

1. 나이트는 오른쪽으로만 간다.
2. 나이트는 위아래로 2칸이내에서만 움직이므로, 세로길이가 3이상이면 모든 이동방법을 사용할 수 있다.
3. 이동 횟수가 4이상(가로칸이 5이상)이라면 이동 방법을 모두 한번씩 사용해야하므로, 가로길이가 7이상이면 적어도 2 번은 오른쪽으로 2칸씩 이동해야한다.
4. 2번 3번 규칙에 입각하여, 세로길이(N)가 3이상이고 가로길이(M)가 7이상이라면, 나이트의 방문 최댓값은 M-2이 될것이다.
5. 세로길이가 3이상이고, 가로길이가 4이상 6이하면 방문 최댓값은 4이다.
6. 세로길이가 3이상이고, 가로길이(M)가 3이하이면 방문 최댓값은 M이다.
7. 세로길이가 2면, 방문 최댓값은 (가로길이(M)-1)/2+1이다.
    (단, 3번 규칙에 의해 방문 최댓값은 4를 넘길 수 없다!)
8. 세로길이가 1이면, 방문 최댓값은 1이다.
9. 4~8번 규칙으로 로직으로 적용한다.

 

 

 

소스 ▽

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

public class Main {// No1783 : 병든 나이트

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] txt = br.readLine().split(" ");

        int N = Integer.parseInt(txt[0]);//세로
        int M = Integer.parseInt(txt[1]);//가로
        int ans = 1;

        switch (N) {
            case 1:
                break;
            case 2:
                ans = (M - 1) / 2 + 1;
                if (ans > 4) {
                    ans = 4;
                }
                break;
            default:
                if (M >= 7) {
                    ans = M - 2;
                } else if (M >= 4) {
                    ans = 4;
                } else {
                    ans = M;
                }
                break;
        }

        System.out.println(ans);
    }
}