[Python] 백준 #1783 - 병든 나이트

문제

---

 

1783번: 병든 나이트

코드

---

My answer

h,w=map(int,input().split())
if(h==1 or w==1):
    answer=1
elif(h<3):
    answer=(w-1)//2+1
else:
    answer=w
if(answer>=5):
    if(h>=3):answer=max(4,5+(w-7))
    else:answer=4
print(answer)

 

Another answer

N,M=map(int,input().split())
if N==1:
    print(1)
elif N==2:
    print(min(4,(M+1)//2))
else:
    print(max(M-2,min(4,M)))

 

풀이

---

우선 코드 설명은 h가 1이면 지금있는 칸 끝이므로 답은 1이된다. 이후 h가 2이면 정답은 (w-1)//2+지금있는 1칸 이된다. 이 방법은 h가 3보다 작으므로 2칸이상 올라갈 수 없기 때문에 2,3번 방법만 이용해서 가는 것이다. 이방법을 이요하면 칸수로 2칸당 한번 방문하는 꼴이돼서 현재 나이트가 첫째칸에 있으므로 전체길이w에서 1을빼주고 남은 칸들 중 2칸당 1번이니 //2를 해주고 맨첫째칸을 밟았으니 결과적으로 (w-1)//2가 된다. 이때 조건문을 h==2로 해준이유는 아래에서 나온다. 우선 방문한칸이 5이상이면 모든 방법을 써야한다. 그런데 위와 같이 계산한 것은 모든방법을 쓴게아니라 특정 제일 좋은방법(greedy)를 통해 푼것으로 그 결과로 h==2일땐 2,3방법으로만 움직였다. 따라서 답이 5이상이면 식을 다르게 만들어줘야한다. 우선 h==2를 정해준 이유와 아래 조건식에서 5+(w-7)이라는 식이 나온이유는 나이트가 시작지점에서 모든방법을 한번씩 이용한다고 해보자. 그럼 w의 위치는 7번째에 있을 것이고 h는 1~4번방법 순서를 어찌됐든 높이가 3인칸을 한번은 지나왔을 것이다. 따라서 h가 3미만이면 모든방법을 한번씩 쓸수가없다. 반대로 3이상이면 모든방법을 쓸 수 있다. 즉 모든방법을 한번씩 쓴 이후에는 아무방법이나 써도되므로 계속 1,4,번만 반복한다고하면 남은 너비만큼 방문할 수 있다. 그래서  모든방법을 한번씩 썼을 때 방문한 5칸+(w-7)칸을 방문할 수 있다. 그리고 max를 써준이유는 위에서 answer이 5이상 나왔을 때 이 조건문을 들어오는데 5이상 나온건 모든방법을 쓰지않고 나온것일 수도 있으므로 모든방법을 한번씩쓰고 계산한결과와 5를넘지않는 4와 비교해야 답이된다. 우선 내 코드는 여기까지다.

아래코드 또한 동일한 방법인데 조건문을 더 간단하게 적은 것같다. 이해가 안가는부분이 있으면 댓글달아주시면 열심히 설명해드리겠습니다. :) 핵심은 아래 코드처럼 h가 1,h가 2,h가 3일 때를 나눠서 풀어야하며 왜 1,2,3으로 분기점을 나눴는지 이해해야 하고 각각 어떤식을 적용하는지 직접해보면서 이해해야한다.