[백준] 1783번: 병든 나이트 - Python

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

1783번: 병든 나이트

아이디어

• n이 1이면 무조건 1칸
• n이 2면 m이 4칸이 최대 아니면 (m-1)//2+1만큼 이동 가능 min으로 판단.(4번 이상 움직이려면 모든 방법을 다 한번이상 사용해야 하는데 그러지 못하니 최대가 4칸임)
• m이 6보다 작거나 같을때 4번 이상으로 움직인다고 하면, 1~4번 방법을 모두 써야 하므로 최댓값은 4가 될 것이고, 최소값은 자신 가로의 길이가 될 것이다.
• 나머지 세로의 길이가 3 이상이고, 가로의 길이가 7이상인 경우는 4방법을 한 번 모두 다 쓰고 나머지는 오른쪽으로 한 칸씩만 가는 방법을 쓰면 되니까 m-2를 하면 됨.

구현

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)

마무리

• 구현은 너무도 간단하지만 이 규칙을 찾기위해 해야할 생각이 너무도 많다.
• 그리디 문제는 규칙과 몇 가지 예외들만 빠르게 찾아내는게 관건이다.