[python] 백준 1783 : 병든 나이트(자세한 풀이)

[python] 백준 1783 : 병든 나이트(자세한 풀이)

1783번: 병든 나이트 (acmicpc.net)

1783번: 병든 나이트

실버 4

그리디

---

접근

가로가 M, 세로가 N이다.

N의 크기에 따라 나이트가 이동할 수 있는 경우의 수가 제한이 되는 부분이 있기 때문에 bfs대신 그리드를 경우의 수에 따라 나눠서 적용하는 방법을 사용해야 한다.

 

문제 조건에 따라 나이트가 이동할 수 있는 경우의 수는 다음과 같이 4가지이다.

문제 조건을 읽어보면, 나이트의 초기 위치는 반드시 맨 왼쪽 아래 구석에 있기 때문에 세로 N의 길이에 따라 나이트의 이동 패턴이 제한된다.

 

N=1의 경우

나이트는 무슨 수를 써도 한 발자국도 움직이지 못하기 때문에 방문횟수는 1이다. (맨 처음 위치)

 

N=2의 경우

나이트의 이동 패턴은 두가지로 제한된다.

그런데 문제 조건에 따르면, 방문횟수가 5가 될때는 나이트가 처음 제시된 4가지의 이동패턴을 적어도 한번씩은 사용을 해야만 한다고 한다.(방문횟수가 4가 될때까지는 아무 조건이 없다.)

 

따라서 N=2인 상황에서는 나이트의 방문횟수가 4를 초과할 수가 없다.

방문횟수가 5가 되는 위치에 도달했다면 4가지 이동패턴을 한번씩 사용했어야 하는데 그럴 수가 없는 상황이기 때문이다. 

 

따라서 M(가로길이)의 값이 7이상이라면 방문횟수는 무조건 4로 고정된다.

M이 8미만일때의 방문횟수는 다음과 같다.

M	방문횟수
1	1
2	1
3	2
4	2
5	3
6	3
7	4

따라서 방문횟수를 간단하게 공식화하면 M+1//2와 같다.

 

결론적으로 M<7 의 경우 방문횟수는 M+1//2, M>=7의 경우의 방문횟수는 4가 되는 것이다. 이를 더 간단하게 

print(min(4, M+1//2))으로도 나타낼 수 있다.

 

 

N>=3 인 경우

세로로 뻥 뚤려있어서 이동의 제약이 사라지게 된다.

구하고자 하는 값이 방문할 수 있는 칸의 최대 개수라는 점과, 방문횟수가 5가 될 때는 4가지 이동패턴을 한번씩은 사용했어야 한다는 점을 염두에 두고 다음과 같은 경우의 수들을 살펴보자.

 

경우의 수 1

가로로 한칸씩만 이동한다면 조건에 따라 나이트 방문횟수의 최댓값은 4가 된다. 4->5로 가지 못하는 이유는 4가지 이동패턴을 한번씩 사용해야 한다는 조건에 어긋나기 때문이다.

따라서 M <= 4의 범위에서 방문횟수는 M이 된다는 것을 알 수 있다.

 

 

방문횟수가 5에 도달할 때까지 4가지 이동패턴을 모두 사용하는 경우의 수(경우의 수 2)

4가지 이동패턴을 모두 사용하는 M=7 구간부터는 방문횟수가 최댓값이 되어야하므로 1칸씩만 이동하면 된다.

아래의 경우도 마찬가지다.

 

방문횟수가 5에 도달할 때까지 4가지 이동패턴을 모두 사용하는 경우의 수(경우의 수 3)

결론적으로 M>6 구간부터는 방문횟수는 M-2로 고정된다.

M=7일때 방문횟수가 5이고, 그 다음부터는 1씩 증가하는 것이 방문횟수의 최댓값이 되기 때문이다.

 

이제 위의 3가지 경우의 수를 M값에 따른 방문횟수의 표로 나타내면 다음과 같다.

M	방문횟수	M	방문횟수	M	방문횟수
1	1	1	1	1	1
2	2	2	1	2	2
3	3	3	2	3	3
4	4	4	2	4	3
x		5	3	5	4
x		6	4	6	4

결국 M <= 4까지의 구간에서는 방문횟수가 M이 되고, 5<=M<=6 의 구간에서는 방문횟수가 4가 되는 것이 최댓값이 된다는 것을 알 수 있다. 이는 m <= 6의 범위에서 print(min(4, m))이고 m>6의 범위에서 print(m-2)가 된다.

 

코드

import sys; input = sys.stdin.readline
n, m = map(int, input().split())
if n == 1:
    print(1)
elif n == 2:
    print(4, (m+1)//2)
elif m <= 6:
    print(min(4, m))
else:
    print(m-2)

 

실버 4라고 하기에는 너무 어려운 문제가 아닌가...