백준 1783 : 병든 나이트(그리디) ****

 

www.acmicpc.net/problem/1783

1783번: 병든 나이트

나이트가 움직일 수 있는 방법

1. (위2, 오1)

2. (위1, 오2)

3. (아1, 오2)

4. (아2, 오1)

 

나이트가 이동하면서 방문할 수 있는 칸의 최댓값은?

단, 이동횟수 4회 이상일 경우, 네 번 방법 모두 사용해야 함.

--> 체스판이 작을 경우. 최대한 1,4를 많이 쓰는 것이 유리.

 

Input : N, M = 체스판의 세로, 가로

Output : 방문할 수 있는 최대 칸 수

 

 

문제 풀이>

단순하게 생각했는데 케이스를 깔끔하게 나누는 게 생각보다 까다로웠다.

다음과 같이 이동이 가능하다.

x축 : +1 or +2

y축: +2,-2 or -1,+1

어떤 이동 스텝을 써도 x축으로는 계속 움직이게 되므로, 오른쪽 이동 횟수가 가장 적은 1,4번 방법을 최대한 많이 이용하는 것이 유리하다.

 

경우의 수를 나눌 땐, 1~4를 모두 사용할 수 있는 경우와 모두 사용할 수 없는 경우를 기준으로 보면 편리하다.

 

 

체스판 시작점 왼쪽 아래를 (0,0)이라 하자. 

 

 

Case 0.

세로 길이(N)=0 : 움직일 수 없다.

 

Case 1.

세로 길이(N) = 2이라 하자.

이 경우에는 가로의 길이가 길더라도, 공간 부족으로 1,4번 방법을 사용하지 못한다. 

2,3번을 이용하면 오른쪽으로 두칸씩 이동하므로 (M-1)//2번 이동할 수 있다.

하지만, 네번 이동하는 순간 1~4를 모두 사용해야한단 규칙이 있으므로, 2,3을 이용해서 이동할 수 있는 것은 최대 3번이다.

--> 처음 위치 + 2,3 번 사용 가능 횟수 

--> 1+min(3, (M-1)//2)

 

Case 2.

세로 길이(N) >= 3이고, 충분히 큰 체스판에 대해서 생각해보자. (M >= 7)

2, 3번 방법을 한번씩 쓴 후에, 1, 4번 방법을 번갈아서 사용하면 된다.

2, 3번을 한번씩 사용한 후에는 (5,0)에 위치하므로, 이때부터 1, 4번은 (M-5)번 사용이 가능하다.

--> 처음 위치 + 1,4번 방법 한번씩 사용 + 2,3번 (M-5)번 반복 

--> 1 + 2+ (M-5)

 

 

Case 3.

세로 길이(N) ≥ 3이고, 가로의 길이가 한정적이라고 해보자. (1~4를 골고루 사용할 수 없는 상황이라고 해보자.)

마찬가지로, 1,4을 최대한 많이 이용해야 하고, 1~4를 모두 사용하지 못한다면 최대로 이동할 수 있는 횟수는 3회이다.

--> 처음 위치 + 1,4번 사용 가능 횟수

--> 1 + min(3, M-1 )

 

1~4를 한번씩 사용했을 때 x축 좌표는 (6,0)이 되므로 M이 7보다 작을 때 위 경우를 사용하면 된다.

 

 

def solve(N,M):
    if N==1: ans = 1
    ## 2,3번 방법만 사용 가능 --> 3번까지만 이동 가능
    elif N==2: ans = 1 + min(3, (M-1)//2) 
    ## N>=3, 위아래 한/두칸 이동 모두 가능
    elif M< 7 : ans = 1 + min(3,M-1)
    else : ans = 1+2+(M-5)
    return ans
    
if __name__=='__main__':
    N,M = map(int,input().split())
    ans = solve(N,M)
    print(ans)

   

 

 

Reference

it-college-diary.tistory.com/entry/그리디-알고리즘-백준-1783번-병든-나이트

[그리디 알고리즘] 백준 1783번 병든 나이트