[Python] 그리디 알고리즘백준 1783번 병든 나이트 풀이 /자세한 그림 풀이...

 

문제

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

입력

첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.

출력

병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.

예제 입력 1 

100 50

예제 출력 1 

48

예제 입력 2 

1 1

예제 출력 2

1

예제 입력 3

17 5

예제 출력 3 

4

 

 

 

 

 

 

아이디어 생각하기

 

먼저 풀기 전, 그림을 그리면서 어떤 규칙이 있는지를 생각해보자. 

 

최대 방문칸만을 구하는 것이므로, 최종 좌표를 구하는 문제가 아니다!

최종좌표를 구하려면... x로 움직이면 막 -1... y로 움직이면 -2... 이차원 배열을 만들고... 그런 걸 생각 안해도 된다. 

 

 

이동 횟수가 4이상 진행되기 위해선  1번부터 4번의 이동 방법을 모두 한 번씩 사용해야 한다.

즉,  칸이 너무 좁아서 방법을 모두 쓸 수 없는 상황일 땐, 

 썼던 방법을 재사용해서 어떻게든 많이 움직여야  최대 방문 횟수를 구할 수 있다!!!!!!

 

 

음~~ 한 번 움직일 때 마다
위로 두칸~ 오른쪽으로 한 칸씩 가니까~ 
총방문칸은 ~ 움직이는 횟수 + 3이겠지????ㅎㅎ~

라는 함정에 빠졌었는데....아니다....

 

지나가는 칸은 방문하는 칸이 아니고,

이동을 마쳤을 때의 위치만 방문칸으로 설정한다. 

 

N = 1일 경우

움직일 수 없기 때문에 방문 가능한 칸은 1칸이다

 

N = 2 일 경우

위 아래로 한 칸씩만 움직일 수 있기 때문에

(1) ↑ 1칸  && → 2칸  (2) ↓ 1칸 &&  → 2칸

 

 

두 가지 이동만 가능하다. 

N = 2일때의 최대 이동횟수는 3, 최대 방문칸은 4이다. 

 

최대방문칸을 구하는 식은

최대방문칸(result) = 이동횟수 + 1

의 식이 성립된다. 

 

왜? 

이동 횟수가 0일땐 그자리에 있기 때문에 1칸

이동 횟수가 1일땐, 시작 칸=> 도착 칸으로 이동하여 2칸

 

방문횟수가 5가 될 때, 4가지의 이동패턴을 적어도 한 번씩은 사용해야 한다. 

, N=2일 때, 가로 M에 따른 최대 방문칸을 정리하면 

 

세로M	최대 방문칸(result)
1	1 //제자리에 있음
2	1
3	2
4	2
5	3
6	3
7 이상 ( 7보다 커도 더 이상 이동 불가)	4

세로 M이 1~6일 때 

result = (m + 1) // 2

식이 성립되고, 세로 m >= 7일시, result는 4라는 조건을 코드에 작성하자.

 

 

 

N = 3 이상일 경우

 

가로 n이 3 이상일때부터 위 아래로의 이동 제약이 없다.

 

세로 m=7일 때부터 칸이 넉넉하여 1~4 모든 방법이 사용 가능하고,

모든방법을 쓰고 난 후엔 

오른쪽으로 한칸만 이동하는 것이 최대한 많이 방문할 수 있는 방법이므로,

 

m = 7일때의 진행방향(그림참조)을 보면

(1) ↑ 2칸  && → 1칸

(2) ↓  2칸 &&  → 1칸

만 사용하여 진행되는 것을 할 수 있다

 

그러나 M이 1~6일 경우, 4가지 이상의 방법을 사용할 수 없다

따라서 최소한의 공간에서 최대한 많이 방문하기 위해선

(1) ↑ 2칸  && → 1칸

(2) ↓  2칸 &&  → 1칸

만 사용하여 이동하게 된다. 

 

 

각자의 최대 방문칸을 표로 정리하면, 

 

 

세로 M	최대 방문칸(result)
1	1 //이동불가능
2	2
3	3
4	4
5	4
6	4
7	5
8	6
9	7

m이 6 이하일 때

m <= 6: #m이 1~6일 때
    result = min(m, 4)

4와 m중 더 작은 쪽이 답인 규칙이 발견되고, 

 

m이 7 이상일 때

m >= 7: #m이 7 이상일 때
    result = m - 2

총 방문칸은 m-2 라는 규칙을 발견할 수 있다

 

 

이를 코드로 작성하자 

 

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

result = 0
# n이 1일 때 무조건 1
if n == 1:
  result = 1
# n이 2일 때
elif n == 2: 
  if m >= 1 and m <= 6: #m이 1~6일 때
    result = (m + 1) // 2 
  elif m >= 7: #7이상일 때
    result = 4
# n이 3 이상일 때
elif n >= 3: 
  if m <= 6: #m이 1~6일 때
    result = min(m, 4)
  elif m >= 7: #m이 7 이상일 때
    result = m - 2
print(result)

 

 

 

하... 이게 뭐라고 며칠동안 끙끙 앓았을까.... 열심히 공부하도록 하자...