[BOJ1783] 병든 나이트

문제

• 병든 나이트가 N*M 체스판 가장 왼쪽아래 위치
• 움직임 4가지 (가로, 세로) 이동
  (1, 2) (2, 1) (2, -1) (1, -2)
• 방문한 칸 수 최대
• 나이트 이동횟수 4번 보다 적지 않으면, 이동 방법 모두 한 번씩 사용
• 이동횟수 4번보다 적은 경우 이동 방법에 제약 없음
• 체크판 크기 주어졌을 때, 나이트가 방문할 수 있는 칸 최대 개수

입력

• N, M (<= 2,000,000,000)

출력

• 병든 나이트가 여행에서 방문할 수 있는 최대 칸 수

설계

• 왼쪽 아래에서 시작하여, 움직일 수 있는 방법을 토대로 세로 길이를 나누어 그리디하게 접근
• N=1 : 움직일 수 없어서 방문수는 시작지점 1
• N=2 : 2, 3번 움직임 이용(이동횟수4번미만 제약없음) min(4, (M+1)/2)
• N=3 : (M<7) 1, 4번 움직임 이용 min(4,M) , (M >=7) M-2
  이동방법 모두 사용하려면 7개의 칸 사용 필요(가로기준 빈 칸 두 개), 이후에 1, 4번 움직임만 이용

피드백

• 그래프만 보면 탐색으로 접근하는 버릇이 들어, 궁리를 해보다가 입력이 너무 커서 분명히 시간초과가 뜰 게 뻔했음
• 도저히 아이디어가 떠오르지 않아서 다른 사람들의 솔루션 참고를 했지만, 이해하는 데에도 정말 오래걸림
• 문제가 불친절한 건지, 내 문제 이해력이 딸리는 건지… 후자가 맞아 보이지만… 티어도 별로 안 높은데 자괴감 드는 문제였음

How I solved(click to github)

---

ref :
BOJ1783
참고 블로그