/ BOJ

BOJ_1783_병든나이트_JAVA

문제 : 병든나이트

링크 : BOJ_1783_병든나이트

접근 방식

나이트는 체스에서의 나이트처럼 이동할 수 있는데, 진행방향은 오른쪽으로밖에 갈 수 없다.

문제에서 확실하게 표현해줬으면 하는 부분이 있었는데, 나이트가 4칸 초과로 이동을 할 때에는 4개의 이동방식을 한 번 이상 사용해야 한다는 점을 확실하게 해 줬으면 했다. 처음에는 4개의 이동방식을 계속해서 바꿔가며 사용해야 하는 줄 알았다.

요점은 4칸 보다 더 많이 이동할 때, 적어도 한 번은 4개의 이동방식을 각각 사용해야 한다는 점, 그리고 나이트는 오른쪽으로밖에 이동하지 못한다는 점을 핵심으로 두고 고민을 해봐야 한다.

조건은 3가지로 나눌 수 있다.

  1. N이 1일 때 : N이 1일 때는 나이트는 이동할 수 없다. 최소한 위, 아래로 한 칸을 이동해야 하기 때문이다.

  2. N이 2일 때 : N이 2일 때는 나이트는 2개의 이동방식만 사용하여 이동할 수 있다. 따라서 M이 아무리 값이 크더라도 최대 4칸까지 이동할 수있다. M이 줄어드는 것에 따라서 이동 가능한 칸은 줄어든다.

  3. N이 3이상일 때 : N이 3 이상이라면, 나이트는 4개의 이동방식을 모두 1번씩 먼저 사용한다. 이것이 가능한 조건은 일단 M이 7보다 커야한다. M이 7일 때 정확 나이트는 4개의 이동방식을 모두 사용하고, 방문한 칸은 5개가 된다. 그 이후에는 어떤 이동방식을 사용해도 상관 없으므로, 이후 가장 많은 횟수를 얻을 수 있는 1번 이동과 4번 이동을 반복하는 식으로 하면 M의 길이에서 7만큼 뺀 값의 칸을 방문할 수 있게 된다. M이 7일 때의 5를 더해주면 식은 M-2가 된다. M이 7보다 작을 때에는, M에 따라서 4개의 이동방식을 모두 사용할 수 없기 때문에 M과 4중에 더 작은 값을 넣어주면 된다.

소스 코드

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

public class BOJ_1783_병든나이트 {

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		if (N == 1) {
			System.out.println(1);
			System.exit(0);
		}

		if (N == 2) {
			int cnt = (M + 1) / 2;
			if (cnt > 4) {
				System.out.println(4);
			}else {
				System.out.println(cnt);
			}
			System.exit(0);

		}

		if(N >= 3) {
			int cnt;
			if(M >= 7) {
				cnt = M-2;
			}else {
				cnt = Math.min(4, M);
			}
			System.out.println(cnt);
			System.exit(0);
		}

	}

}