Baekjoon Online Judge 1783번 파이썬. 그리디.

문제 링크
https://www.acmicpc.net/problem/1783

1783번: 병든 나이트

N = 1
이동할 수 없으므로 방문 할 수 있는 칸 수는 1.

N = 2
위로 한 번,오른쪽 두번과 아래로 한 번, 오른쪽 두번. 이 두가지 이동패턴만 가능하다. 그런데, 4번 이상 이동하면 이동 패턴을 한번씩만 사용해야 한다.
그리고 이는 M의 길이에 따라 달라진다. M이 6보다 커질 때부터 이동 횟수가 4번이 되기 때문에 더 이상 이동할 수 없게 된다.

열의 크기 / 방문한 칸 수
M = 1 -> 1
M = 2 -> 1
M = 3 -> 2
M = 4 -> 2
M = 5 -> 3
M = 6 -> 4
M = 7 -> 4
그래서 ‘print(min(4, M+1//2)’으로 나타낼 수 있다.

3 <= M <= 6
여기부터는 N이 3보다 커서 행을 생각할 필요가 없다.
오른쪽으로 이동하면서 이동 횟수가 4를 넘지 않거나 모든 방향을 다 이동했을 경우의 수가 M이 6인 경우이므로 열이 6보다 작거나 같을 경우엔 print(min(4,m))

그 외에는 직접 해보면서 M-2라는 규칙을 찾았다.

정답 코드

import sys
N, M = map(int,sys.stdin.readline().split())

if N == 1:
  print(1)
elif N == 2:
  print(min(4,(M+1)//2))
else:
  if M <= 6:
    print(min(4,M))
  else:
    print(M-2)