[JAVA][BOJ][S3] 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보다 작거나 같은 자연수이다.

출력

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

풀이

이 문제에서 중요한 것은 M(가로) 방향은 오른쪽으로만 갈 수 있고, N(세로) 방향은 위아래로 모두 갈 수 있다는 것이다 또한 N은 1칸, 2칸만 움직이기 때문에 세로 길이가 3 이상만 된다면 자유롭게 움직일 수 있다

그렇기 때문에 N이 3 이상만 된다면, M에 최댓값을 맞춰야 한다

또한 이동 횟수가 4번 이상(방문한 칸이 5칸 이상)이면 이동 방법을 한 번씩 다 사용해야 하기 때문에, 다 쓸 수 있는 방법이 없다면 4칸으로 한정해야 한다
N>=3, M>=7일 때는 무조건 이동 방법을 한 번씩 모두 사용해 이동 횟수를 4번 이상으로 만들어야 최댓값이 된다

 

위의 설명을 다시 정리해 보면, if문의 분기점은 네 가지가 있다

1. 세로 길이가 1이면 무조건 움직이지 못한다
        if(N==1) ans = 1;
2. 세로 길이가 2일 때는 옆으로 2칸씩만 움직일 수 있다 1칸씩 움직이는 방법을 사용할 수 없기 때문에, 최댓값은 4가 된다
        else if (N==2) ans = Math.min((M+1)/2, 4);
3. 세로 길이가 3 이상이고 가로 길이가 7 미만일 때는, 모든 이동 방법을 사용할 수 없기 때문에 최댓값은 4가 된다
        else if(M<7) ans = Math.min(M, 4);
4. 세로 길이가 3 이상이고 가로 길이가 7 이상일 때는, 모든 이동 방법을 무조건 사용하고(ans+4) 남은 M만큼(ans+=M-6) 이동한다
        else ans = M - 2;

코드

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

public class S3_1783_병든나이트 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Long.parseLong(st.nextToken());
        long M = Long.parseLong(st.nextToken());
        
        long ans = 0;
        
        // 세로 길이가 1이면 무조건 움직이지 못한다
        if(N==1) ans = 1;
        // 세로 길이가 2일 때는 옆으로 2칸씩만 움직일 수 있다
        // 1칸씩 움직이는 방법을 사용할 수 없기 때문에, 최댓값은 4가 된다
        else if (N==2) ans = Math.min((M+1)/2, 4);
        // 세로 길이가 3 이상이고 가로 길이가 7 미만일 때는,
        // 모든 이동 방법을 사용할 수 없기 때문에 최댓값은 4가 된다
        else if(M<7) ans = Math.min(M, 4);
        // 세로 길이가 3 이상이고 가로 길이가 7 이상일 때는,
        // 모든 이동 방법을 무조건 사용하고(ans+4) 남은 M만큼(ans+=M-6) 이동한다
        else ans = M - 2;

        System.out.println(ans);
    }

}

결과

 

#자바 #java #boj #백준 #알고리즘