반응형
문제
https://www.acmicpc.net/problem/1783
병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.
- 2칸 위로, 1칸 오른쪽
- 1칸 위로, 2칸 오른쪽
- 1칸 아래로, 2칸 오른쪽
- 2칸 아래로, 1칸 오른쪽
병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.
체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.
입력
첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.
출력
병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.
코드
import sys
input=sys.stdin.readline
n, m=map(int, input().split())
if n == 1:
print(1)
elif n == 2:
print(min(4, (m-1)//2+1))
elif m <= 6:
print(min(4, m))
else:
print(m-2)
문제 해결
처음엔 DFS와 BFS를 이용하는 문제인 줄 알았으나, 나이트의 움직임이 4가지로 정해져 있어서 위아래와 오른쪽 방향으로만 정해져있어서 조건 분기, 그리디로 풀 수 있는 문제였다.
반응형
'Problem Solving > 백준' 카테고리의 다른 글
[백준] 1874번: 스택수열 - [Python/파이썬] (0) | 2023.04.14 |
---|---|
[백준] 1850번: 최대공약수 - [Python/파이썬] (0) | 2023.04.13 |
[백준] 1747번: 소수&팰린드롬 - [Python/파이썬] (0) | 2023.04.13 |
[백준] 1744번: 수 묶기 - [Python/파이썬] (0) | 2023.04.13 |
[백준] 1725번: 히스토그램 - [Python/파이썬] (0) | 2023.04.13 |