모각코 PS스터디 / 백준 1783 병든 나이트

모각코 PS스터디

왜인지 모르겠는데 PS는 하고 나서 포스팅 하는 걸 자꾸 까먹는다.
이번주 스터디 한 세 문제를 차례로 포스팅해보려고 한다.

문제와 풀이

---

문제 링크 : 백준 1783번 - 병든 나이트

👇펼쳐서 코드와 해설 읽기

이 문제도 역시 그리디(greedy) 카테고리의 문제다.
얼핏 보면 탐색 같지만, 표본 수(2,000,000,000)를 보면 탐색으로 했을 때 무조건 타임아웃이 날 거란 걸 생각해볼 수 있다.

충족할 조건은 2가지다.

1. 이동횟수를 최대화할 것.
2. 이동방식을 충족할 것. (밟은 발판 갯수가 5개 이상 시에만)
3. 나이트의 이동경로는 다음 네가지다
   1. 2U 1R
   2. 1U 2R
   3. 1D 2R
   4. 2D 1R

네 가지 이동을 완수하는 케이스를 먼저 생각해보기로 했다.
네 가지 이동을 완수하고 나서도 시작점에 가까운 최소점을 구한다면, 거기서 부터 계산한 이동칸수가 최대 칸수가 될 것이다.

방향	이동계산(필요칸수)	비고
오른쪽으로	1 + 2 + 2 + 1 => 6 + 1 => 7	가로 최소 7칸 확보 필요
위로	2 + 1 = 3
아래로	2 + 1 = 3	위/아래는 상계되므로 세로 최소 3칸 확보 필요

즉, 세로3 가로7 이하면 네가지 이동을 완수할 수 없다.
즉2, 세로3 가로7만 넘으면 칸수가 몇이 되든 동일한 방법으로 최대 칸수를 구할 수 있다. (3*7 위치에서, 1 & 4번 이동경로를 반복하여 옆으로 한칸씩 이동하는 방법)

경우의 수를 따라 수도코드를 작성해보았다.

• n이 1이면 움직일 수가 없다
• n이 2면 (m + 1) / 2번만 움직일 수 있다. 그것도 최대 4칸까지만(5칸부터는 이동방법 제약이 있으니까)
• n이 3부터는 m에 따라 발자국이 결정된다
  • m이 7이 안되면
    • 무조건 가로로 한칸씩 움직인다. 그것도 최대 4칸까지만 (5칸부터는 이동방법 제약이 있으니까)
  • m이 7이상이면
    • 위에 적은 조건들을 만족한다(네가지 이동방법 만족). m - 7 + 5라서, 최종적으로 m - 2가 된다.

주요한 분기문 로직이 다 작성되었다.
그대로 코드로 옮겼다. 코드가 어떤 수도코드를 구현한 것인지 옆에 주석으로 붙였다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.close();
        int footprint = 0;

        if (n == 1)
            footprint = 1;  // n이 1이면 움직일 수가 없다
        else if (n == 2)
            footprint = (m + 1) / 2 > 4 ? 4 : (m + 1) / 2; //n이 2면 (m + 1) / 2번만 움직일 수 있다. 그것도 최대 4칸까지만(5칸부터는 이동방법 제약이 있으니까)
        else
            if (m < 7) // m이 7이 안되면
                footprint = m > 4 ? 4 : m; // 무조건 가로로 한칸씩 움직인다. 그것도 최대 4칸까지만 (5칸부터는 이동방법 제약이 있으니까)
            else // m이 7이상이면
                footprint = m - 2; // '네가지 이동방법 만족' 조건을 만족한다. 조건을 만족하는 위치(7), 조건을 만족한 발자국 수(5)를 감안하면 m - 7 + 5, 즉 m - 2가 된다.

        System.out.println(footprint);
    }

}

마무리

---

탐색 문제였으면 솔직히 못 풀었다. ㅋㅋㅋ...