[그리디 알고리즘] ★★ 1783번 - 병든 나이트

[백준] 1783번 - 병든 나이트

1) 문제 해결 아이디어

처음에는 방향벡터를 설정하여 직접 나이트를  움직여야한다고 생각했는데 

이 문제는 그런 방식으로 푸는 문제가 아니었다.

 

세로(n)이 1이면 m의 값과 상관없이 어느 방향으로도 이동할 수 없으므로 항상 1이다.

세로(n)이 2라면 2, 3번 방법으로만 이동할 수 있다. 방문한 칸이 4개가 넘어가면 모든 방법을 다 써야하기 때문에 움직이고 싶어도 더이상 움직일 수 없다. 여기서 최댓값은 4이고 m에 값에 따른 방문칸 수는 아래와 같으므로 이를 수식으로 나타내면 (m+1) // 2 이다.

m	방문칸 수	이동 방법(y) 2, 3 방법은 무조건 +2 만 가능 ( ) 안에서는 자유롭게 이동 가능
1	1	1
2	1	1
3	2	1 + (2)
4	2	1 + (2)
5	3	1 + (2 + 2)
6	3	1 + (2 + 2)
7	4	1 + (2 + 2 + 2)
8	4	1 + (2 + 2 + 2)
9	5	1 + (2 + 2 + 2) + 2

 

세로(n)이 3이상일 때, 가로(m)이 6이하이면 모든 방법을 쓸 수 가 없다. 1번과 4번만 이용할 수 있다.

 

 

2) 소스코드

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

if(n == 1):
  res = 1
elif(n == 2):
  # 2, 3, 방향으로 밖에 못 움직임(m값과 상관없이 최대값은 4)
  res = min(4, (m + 1) // 2)
else:
  # 1, 2, 3, 4 방향 다 가능
  if(m <= 3):
    res = m
  else:
    if(m <= 6):
      res = min(4, m) 
    else:
      res = m -2
print(res)