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

 

 

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

if n==1 :
    ans = 1
elif n==2 :
    ans = min(4, (m-1)//2 + 1)
elif m < 7 :
    ans =  min(4, m)
else :
    # n>=3 and m>=7
    ans = m - 2

print(ans)

 

 

총 4가지의 케이스로 나누어 풀었다.

 

1) 세로 길이가 1인 경우 : 위 아래로 움직일 수 없으므로, 방문한 칸의 개수는 무조건 1개이다.

 

2) 세로 길이가 2인 경우 : 위 아래로 1칸 씩 밖에 움직이지 못하기 때문에, 최대 방문 개수는 4개일 것이다.

따라서 m 에 따라 최대 4개의 칸을 방문한다. (m-1)//2 + 1 이란 식은 직접 m에 따른 개수를 구함으로써 도출해냈다.

m = 1,2 -> 1개

m = 3,4 -> 2개

m = 5,6 -> 3개

m = 7,8,9,10 -> 4개

 

3) 세로 길이가 3이상이고, 가로 길이는 7보다 작을 경우 : 이 경우도 어쨌든 최대 방문 개수가 4개일 것이다.

왜냐하면 4가지 이동 방법을 다 쓰는 경우는 세로가 최소 3이상이여야 되고 가로도 최소 7이상이여야 충족할 수 있다.

이 경우에는 위 아래로 2칸을 이동하고 오른쪽으로 한 칸씩 이동하는 방법을 사용하면 최대로 이동할 수 있다.

따라서 m의 길이만큼 칸을 방문할 수 있다.

 

4) 마지막으로 세로 길이가 3이상이고, 가로 길이도 7이상일 경우 : 먼저 4가지 이동방법을 모두 사용하고 시작한다고 가정하자. 그럼 세로 1칸, 가로 7칸에 위치할 것이며 이때 방문한 칸의 개수는 5개 이다.

여기서부터는 최대로 칸을 방문하기 위해 위 아래로 2칸씩 움직이며 오른쪽으로 1칸씩 움직이면 된다.

따라서 5 + (m - 7) = m - 2 칸 만큼 방문하 수 있다.