[백준] 1783번: 병든 나이트(그리디, 구현)

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

1783번: 병든 나이트

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();	// 세로
		int M = scan.nextInt();	// 가로
		int visitRoom = 1;		// 방문할 수 있는 칸의 수
		
		if(N == 1)	// 세로길이가 1 => 처음에 있는 칸만 가능
			visitRoom = 1;
		else if(N == 2) {	// 세로 길이가 2 => 오른쪽으로는 무조건 2칸만 갈 수 있음.
			if(M>=7)	// 오른쪽으로 3번 갈 수 있음(6칸) 
				visitRoom += 3;
			else if(M<7 && M>=5)	// 오른쪽으로 2번 갈 수 있음(4칸)
				visitRoom += 2;
			else if(M == 3 || M == 4)	// 오른쪽으로 1번 갈 수 있음(2칸)
				visitRoom += 1;
				
		}
		
		// 세로 길이가 3이상인 경우 => 2칸 위로, 2칸 아래로 가면서 오른쪽 길이만 판단한다.
		else {
			if(M > 6) {	// 이동 횟수가 4번 이상이 되는 최소 가로의 길이
				visitRoom += 4;	// 이동 횟수 4번
				M -= 7;	// 4가지 방법을 사용한 후 최대 개수 구하기
				visitRoom += M;	// 나머지는 오른쪽으로 1칸씩 가면 되므로 남은 가로길이만큼 더한다.
			}
			else {	// 이동 횟수가 4번이 안되는 가로의 길이 => 최대 갈 수 있는 칸의 개수 판별.
				if(M>=4 && M<=6)	// 오른쪽으로 3번 갈 수 있음.
					visitRoom += 3;
				else if(M == 3)	// 오른쪽으로 2번 갈 수 있음.
					visitRoom += 2;
				else if(M == 2)			// 오른쪽으로 1번 갈 수 있음.
					visitRoom += 1;
			}
		}
		System.out.println(visitRoom);
		scan.close();
	}

}

풀이

모든 케이스를 다 생각해가며 구현했다. 문제 풀면서도 테스트 케이스는 다맞았으나 반례가 있을 것 같았는데 통과...

문제에서 주어진 조건은 다음과 같다.

 

N * M 크기의 체스판(N = 세로, M = 가로)

병든 나이트가 움직일 수 있는 방법은 4가지.

 

1번. 2칸 위로, 1칸 오른쪽

2번. 1칸 위로, 2칸 오른쪽

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

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

 

최대한 많은 칸을 방문하길 원하고, 만약 나이트의 이동 횟수가 4번 이상일 경우 위 4가지 방법을 최소 한번은 사용해야 한다.

 

조건을 잘보면 위와 아래로는 가지만, 항상 오른쪽으로 간다.

따라서, 가로의 조건을 잘 따져가며 풀어야 한다.

또한 나이트의 이동 횟수가 4번 이상이 되려면 N의 크기는 3이상이어야 하고, M의 크기는 7이상이어야 한다.

따라서 세로의 크기(N의 크기)가 1일때, 2일때, 3이상일때 총 세 가지로 나누어 풀었다.

세로의 크기가 2일때는 위 방법중 2번, 3번만 사용할 수 있다.

왜냐하면 1번과 4번의 경우 위로 2칸을 가거나 아래로 가야하지만, 세로의 크기가 2이기 때문에 체스판에서 벗어나기 때문이다.

세로의 크기가 3일때는,

이동 횟수가 4번 이상이 되느냐, 이동 횟수가 3번이냐, 2번이냐, 1번이냐 등에 따라 조건을 나눠주면 된다.

 

 

 

풀면서도 너무 복잡한 것 같아서 다른 풀이들을 참고해봤다.

import java.util.*;
public class Test{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		int cnt =0;
		if(n==1)
			cnt = 1;
		else if(n==2)
			cnt = (int)Math.min(4, (m+1)/2);
		else
		{
			if(m<7)
				cnt = Math.min(4, m);
			else
				cnt = m-2;
		}
		System.out.println(cnt);
	}
}

 

 

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

class Main {
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int m = Integer.parseInt(tokenizer.nextToken());
        if (n == 1) {
            System.out.println(1);
        } else if (n == 2) {
            System.out.println(Math.min(4,(m+1)/2));
        } else {
            if (m <= 6) System.out.println(Math.min(4,m));
            else System.out.println(m-2);
        }
    }
}

 

허허 ...