[python/백준/그리디] 1783 : 병든 나이트

문제

풀이

• 원래는 가로, 세로 길이 전부 다 고려해야한다 생각해서 case를 가로/세로 를 기준으로 다 나눴었다.
• 하지만 이 방법은 머리아프고ㅜ 예외 사항이 너무 많아, 세로를 기준으로 case를 나눈 뒤, 가로 길이를 고려해주었다.
• 이 문제는 병든 나이트가 항상 오른쪽으로 가므로, 오른쪽이 최대가 되는 경우를 고려해줘야한다( 이 부분이 조금 어려웠다)
• 코드에 주석을 잘 달아뒀으니 코드를 보고 이해하자!

코드

from math import ceil

n,m = map(int,input().split())
result = 0

# 세로 길이가 2라면
if n==2:
    # 세로 길이가 2라면, 절대 1,2,3,4 이동방법을 다 사용할 수 없다. (다 사용하려면 세로 길이가 최소한 3은 되어야 한다)
    # 따라서 세로 길이가 2일 때, 1,4번만 사용해 5번 움직일 수 있더라도, 최대 경우의 수는 4이다.
    # 5번 이상 움직일 수 없을 경우에는, 
    # 오른쪽으로 두 칸 움직이고 위,아래로 한 칸 움직이는 경우의 수만 가능하므로
    # m/2의 반올림 값이다.
    result = min(4,ceil(m/2))
        
# 세로 길이가 1일 때
elif n ==1:
    result = 1

# 세로 길이가 3 이상일 떄         
elif n>=3:
    # 가로 길이가 6 이하일 때, 경우의 수는 
    # m개의 길이 만큼(오른쪽으로 1씩) 움직일 수 있는데, 단 5번 이상일 경우 불가능 하다 
    # 5번 이상 움직이면 1,2,3,4번을 포함해서 움직여야 하는데 위 조건을 만족하려면 길이가 최소한 7은 되어야 하기 때문이다. 
    if  m < 7:
        result = min(m,4)
    else:
        result = 5+(m-7) # 1,2,3,4를 포함 = 5칸 차지, m-7개 길이 만큼 움직이기 (7개는 1,2,3,4에서 움직인 가로 길이)

print(result)