병든 나이트
-
[백준 1783번] 병든 나이트 (Java 풀이)Algorithm/Greedy Algorithm 2022. 3. 11. 00:44
백준알고리즘 1783번 : 병든 나이트 처음 보았을 때 조금 까다롭게 느껴졌는데, 규칙을 찬찬히 쪼개면서 생각해보니 어렵지 않게 풀렸다. 드물게 switch~case문을 사용하기에 적합한 문제였던 것으로 보인다. 풀이 과정 1. 나이트는 오른쪽으로만 간다. 2. 나이트는 위아래로 2칸이내에서만 움직이므로, 세로길이가 3이상이면 모든 이동방법을 사용할 수 있다. 3. 이동 횟수가 4이상(가로칸이 5이상)이라면 이동 방법을 모두 한번씩 사용해야하므로, 가로길이가 7이상이면 적어도 2 번은 오른쪽으로 2칸씩 이동해야한다. 4. 2번 3번 규칙에 입각하여, 세로길이(N)가 3이상이고 가로길이(M)가 7이상이라면, 나이트의 방문 최댓값은 M-2이 될것이다. 5. 세로길이가 3이상이고, 가로길이가 4이상 6이하면 ..