[BOJ] 1783 - 병든 나이트 JAVA

www.acmicpc.net/problem/1783

1783번: 병든 나이트

문제

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

입력

첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.

출력

병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.

예제 입력 1

100 50

예제 출력 1

48

예제 입력 2

1 1

예제 출력 2

1

예제 입력 3

17 5

예제 출력 3

4

예제 입력 4

2 4

예제 출력 4

2

예제 입력 5

20 4

예제 출력 5

4

 

 

 

 

 

 

 

풀이 .

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());  // height
        int m = Integer.parseInt(st.nextToken());  // width

        int ans = 0;
        if(n == 1) ans = 1;
        if(n == 2) ans = Math.min(4, (m+1) / 2);
        if(n >= 3) {
            if(m >= 7) {
                ans = m - 2;
            }else {
                ans = Math.min(4, m);
            }
        }
        System.out.println(ans);
    }
}

 

문제의 조건 설명이 불친절해서 성질만 잔뜩 돋군 문제.

 

결국 요구사항을 제대로 이해하지도 못하고 정답을 확인했다.

 

문제의 요구조건을 자세히 풀어쓰면 아래와 같다.

 

 

나이트가 매 순간 이동할 위치를 선택하여 이동할 때 방문할 수 있는 칸의 최대값을 구해야 한다.

(h, w)일 때 (-2, 1), (-1, 2), (1, 2), (2, 1) 이렇게 네 가지 경우의 이동 가능.

 

 

 

(제한 조건)

1. 우선 나이트의 시작위치가 없다. 나이트의 시작 위치는 NxM 사이즈에서 임의적으로 선택할 수 있다.

 

2. 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다?

-> 4개 이상의 칸을 방문하기 위해서는 나이트의 네 가지 이동 방법을 모두 사용해야만 한다. 

-> 즉, 3개 이하의 방법만 사용하면서 4번 이상 이동할 수 없다. (= 시작점 포함 5칸 이상 방문할 수 없다)

 

3. 이동 횟수가 4번보다 적은 경우에는 이동 방법에 대한 제약이 없다.

-> 3번 까지만 이동한다면(= 시작점 포함하여 4칸만 방문한다면) 네 가지 이동 방법 중 어떤 방법을 이용하거나 이용하지 않는 것은 자유롭게 선택 가능하다.

 

 

 

(경우의 수)

주어진 경우에서 경우의 수를 셋으로 나누어 생각할 수 있다.

 

1. 높이가 1인 경우

-> 나이트의 네 가지 이동 방법 모두 높이를 최소 1칸은 변경해야 한다.

-> 즉, 체스판의 높이가 1이 전부라면 아무 칸으로도 이동할 수 없다는 뜻이다.

-> 단, 시작 위치는 자유롭게 정할 수 있기 때문에 이 경우 답은 1이 된다.

 

2. 높이가 2인 경우

-> (-1. 2), (1, 2) 두 가지 이동 방법만 사용할 수 있다.

-> 이를 식으로 나타내면 (width + 1) / 2 이다.

-> 단, 위의 제한조건 2에 의해 네 가지 방법을 다 사용하지 않는다면 최대 이동횟수는 3번이 전부이다. (= 시작점 포함 4칸)

-> 따라서 Math.min(4, (width + 1) / 2)가 답이 된다.

 

3. 높이가 3 이상인 경우

-> 이 경우는 다시 넓이가 7 이상인지 아닌지로 나뉘게 된다. (= 네 가지 이동 방법을 모두 사용할 수 있는지 아닌지)

 

3.1 넓이가 7 이상인 경우 (= 네 가지 이동 방법 모두 사용 가능한 경우)

-> 높이가 3 이상이기 때문에 (-2, 1), (2, 1) 이동도 사용이 가능하다.

-> 일단 네 가지 이동 방법을 한 번씩 사용하면 오른쪽으로 6칸 움직이게 된다. (현 가로 위치 7)

-> 여기에서 (-1, 2), (1, 2) 두 이동에 대해서 방문 칸이 없는 컬럼이 하나씩 발생한다. (현재 방문한 칸이 존재하는 컬럼 5개)

-> 그 이후로는 최대한 많은 칸을 방문하는 것이 목적이기 때문에 열을 한 칸 씩만 이동하는 (-2, 1), (2, 1)만 번갈아가며 사용한다. 즉, 열 1칸 당 방문 칸 1개가 추가된다.

-> 따라서 총 열의 개수 -2를 해주면 답이 된다.

 

3.2 넓이가 7 미만인 경우 (= 네 가지 이동 방법을 모두 사용하지는 못 하는 경우)

-> 높이가 3 이상이기 때문에 (-2, 1), (2, 1) 이동도 사용이 가능하지만 그래봤자 네 가지 이동 방법을 전부 사용할 수는 없다. 즉, 답은 4를 넘길 수 없다.

-> 어차피 4를 못 넘길 거 굳이 열을 많이 잡아먹는 (-1, 2), (1, 2)를 사용할 필요가 없다.

-> (-2, 1), (2, 1)만 번갈아가며 사용하며 열마다 한 개의 방문 칸을 만들어 준다.

-> 단, 제한 조건 2에 의해 Math.min(4, width)가 정답이 된다,