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

 

예전에 무진장 겁먹고 못풀었던 문제

정답코드 먼저 살펴보자

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

if n == 1 :
  print(1)
elif n == 2 :
  print(min((m + 1) // 2, 4))
else :
  if m < 7 :
    print(min(m, 4))
  else :
    print(m - 2)

 

핵심은 1,2,3,4 조건의 경우 무조건 오른쪽으로 움직인다는 거다.(왼쪽으로는 돌아올수 없다.)

4번 다 완료하면 오른쪽으로 이동한 수는 6이 된다.

왠지 6이 기준점이 될것 같았다. 

 

n이 1이면 이동은 불가능해서 1

n이 2이면 최대 4의 경우이거나 m을 2로 나눈 경우중 최솟값의 가지수를 가지게 된다

n이 3이상이면 위로 혹은 아래로 이동하는 경우의 수는 제약을 받지 않으므로 m의 경우를 분기처리 해야한다.

    m이 7미만 일경우에는 모든 조건을 하나씩 썼거나 조건에 따라 이동했거나 둘중 하나다. 매번 1칸씩 이동할수도 있으므로 최대의 경우의 수를 가정해서 최솟값을 찾자

    m이 7이상일 경우에는 오른쪽으로 2칸씩 이동하는 경우를 무조건 1번씩 사용하고 오른쪽으로 1칸씩 이동하는경우의 수만 사용하면 m-2가 최댓값이 된다!

 

 

https://www.acmicpc.net/problem/1783

1783번: 병든 나이트