문제
병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.
- 2칸 위로, 1칸 오른쪽
- 1칸 위로, 2칸 오른쪽
- 1칸 아래로, 2칸 오른쪽
- 2칸 아래로, 1칸 오른쪽
병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.
체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.
입력
- 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다.
- N과 M은 2,000,000,000보다 작거나 같은 자연수이다.
출력
- 병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.
풀이
- 갈수 있는 방향이 오른쪽밖에 없다.
⇒ 가능하면 오른쪽으로 적게 가는게 최대이다.
- 오른쪽으로 적게가는 방법은 (1, 4) → (2, 3) 순이다.
알고리즘
- 세로의 길이가 3이상이면 1번과 4번만 쓴다. ( 4가지 다 쓸 순 있다. )
a. 가로의 길이가 7이상이면 가로의 길이-2
b. 가로의 길이가 7미만 4이상이면 4
c. 가로의 길이가 4미만이면 가로의 길이
- 세로의 길이가 2이면 2번과 3번만 쓴다. ( 4가지 다 쓸 수 없다. )
a. 가로의 길이가 7이하면 가로의길이/2를 올림
b. 가로의 길이가 7초과면 4
- 세로의 길이가 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