알고리즘 풀이 - 백준 1783(병든 나이트, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

병든 나이트가 NxM 크기의 체스판을 여행 방문할 수 있는 최대의 수를 구하는 문제

 

 

2. 풀이

 

나이트가 병이 많이 들었는지 아래와 같은 방식으로만 체스판 위에서 움직일 수 있다.

 

기본적으로 오른쪽으로만 갈 수 있는데, 높이 또한 제대로 주어지지 않으면 이동 또한 제한이 걸린다는 것을 알 수 있다.

 

이 문제는 다음과 같이 풀 수 있다. 이 내용을 직접 그려가면서 해보면 쉽게 이해할 수 있다!

 

① 높이(세로) 또는 너비(가로)가 1인 경우에는 현재 위치에서 절대 움직일 수 없다.

  ▶ 첫 위치 하나만 방문 가능하다.

② 높이(세로)가 2라면 2가지 방향(1상 2우, 1하 2우)만 가능하여 다음과 같이 이동 가능하다.
   ⅰ) 너비(가로)가 3 이하이면(2 또는 3), 1회 이동 가능
   ⅱ) 너비(가로)가 5 이하이면(4 또는 5), 2회 이동 가능
   ⅲ) 너비(가로)가 7 이하이면(6 또는 7), 3회 이동 가능
   ⅳ) 4 방향을 모두 쓸 수 없어 너비가 더 넓은 경우는 의미가 없다.

  ▶ 따라서, (너비(가로) + 1) / 2 또는 4번 중 더 작은 횟수로 이동이 가능하다.

③ 높이(세로)가 3이상인데, 너비(가로)가 7 미만인 경우, 모든 방향 사용은 불가하여 다음과 같이 이동 가능하다.
   ⅰ) 기본적으로 최대 이동 가능 횟수는 2방향만 사용하는 것이다.(2상 1우, 2하 1우) 따라서, 최대 열의 길이 만큼 방문이 가능하다.
   ⅱ) 다만, 4방향을 다 사용하지 못하므로 최대 이동 가능은 4이다.

  ▶ 따라서, 4번 혹은 너비(가로) 중 더 짧은 값이 답이 된다.

④ 높이(세로)가 3이상이며, 너비(가로)가 7이상인 경우, 모든 방향 이동이 가능해 다음과 같이 이동 가능하다.
   ⅰ) 기본적으로 최대 이동 가능 횟수는 2방향만 사용하는 것이다.(2상 1우, 2하 1우) 따라서, 최대 열의 길이 만큼 방문이 가능하다.
          - 하지만, 4번 이상 이동 시, (1상 2우, 1하 2우)도 1회씩 사용해야 하며, 그에 따라 2개의 열이 낭비된다.

  ▶ 따라서, 너비(가로) - 2 만큼 이동이 가능하다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        
        int ans = 0;
        System.out.println(travel(n, m));
        br.close();
    }
    
    private static int travel(int n, int m){
        // n이 1 또는 m이 1이라면 이동 자체가 불가하다.
        if(n==1 || m==1) return 1;
        
        // n이 2인 경우, 최대 4번만 움직일 수 있다.
        // 1상 2우, 1하 2우의 2가지만 가능한데, 
        // m이 1, 2면 1개 / m이 3, 4면 2개 / m이 5, 6이면 3회 / m이 7이상이면 4번 이동 가능하다.
        if(n==2) return Math.min(4, (m+1)/2);
        
        // m이 7 미만이라면 2상 1우, 2하 1우의 2가지만 써서 최대한 촘촘히 움직여야 한다.
        // 어차피 4방향을 모두 써서 이동할 수 없어서 최대 4회만 가능하다.
        // 오른쪽으로는 1번씩만 간다면 결국 총 횟수는 M번 또는 4번이다. 그 중 더 작은 수로 한다.
        if(m < 7) return Math.min(4, m);
        
        // 위의 조건문을 모두 피했다면 4방향이 모두 가능한 경우만 남는다.
        // 이 때에도, 무조건 2상 1우 또는 2하 1우만 할 때가 최적이지만, 
        // 4방향을 모두 써야 하기 때문에 1상 2우, 1하 2우를 1번씩은 써야 한다.
        // 따라서, 2개의 열은 단순 소모되므로 m-2를 반환한다.
        return m-2;
        
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.