[Python] 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, 4) → (2, 3) 순이다.

알고리즘

1. 세로의 길이가 3이상이면 1번과 4번만 쓴다. ( 4가지 다 쓸 순 있다. )

   a. 가로의 길이가 7이상이면 가로의 길이-2

   b. 가로의 길이가 7미만 4이상이면 4

   c. 가로의 길이가 4미만이면 가로의 길이

2. 세로의 길이가 2이면 2번과 3번만 쓴다. ( 4가지 다 쓸 수 없다. )

   a. 가로의 길이가 7이하면 가로의길이/2를 올림

   b. 가로의 길이가 7초과면 4

3. 세로의 길이가 1이면 1

병든 나이트 이동 종류

답

import sys
from math import ceil

input = sys.stdin.readline


def sickKnight(n, m):
    if n == 1:
        return 1
    elif n == 2:
        if m > 7:
            return 4
        else:
            return ceil(m / 2)
    else:
        if m >= 7:
            return m - 2
        elif m > 4:
            return 4
        else:
            return m


if __name__ == "__main__":
    N, M = map(int, input().split())
    res = sickKnight(N, M)
    print(res)

짧은 답안

• 1을 더하고 나누므로 math.ceil이 필요하지 않다.

• min함수를 사용해 if~else문이 줄었다.

import sys

input = sys.stdin.readline


def sickKnight(n, m):
    if n == 1:
        return 1
    elif n == 2:
        return min(4, (m+1)//2)
    else:
        if m >= 7:
            return m - 2
        else:
						return min(4, m)


if __name__ == "__main__":
    N, M = map(int, input().split())
    res = sickKnight(N, M)
    print(res)

---

‼️범위를 하나 틀려서 80%에서 한 번 틀려서 멘탈 나갈뻔했다.. 범위 잘 확인하자‼️

Uploaded by Notion2Tistory v1.1.0