[파이썬, 자바] BOJ_1783(병든 나이트)

문제

 

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

1783번: 병든 나이트

---

 

해설

 

이 문제는 이해하는데 좀 오래걸렸다..

이해한 후에는 규칙만 찾으면 쉽게 풀 수 있는 문제였다.

 

문제를 잘 살펴보면

• 1. 2칸 위로, 1칸 오른쪽
  2. 1칸 위로, 2칸 오른쪽
  3. 1칸 아래로, 2칸 오른쪽
  4. 2칸 아래로, 1칸 오른쪽
• 이동 횟수 > 4라면
  위의 4가지 이동 방법을 모두 한 번씩 사용해야 함.
• "방문할 수 있는 칸"에는 가장 처음 밟고 있는 칸도 포함.

이라는 것을 알 수 있다.

 

위의 내용을 잘 생각하며, 그림을 그려서 경우를 하나 하나 따져보면 규칙을 쉽게 찾을 수 있다.

 

1) n = 1일 때,

    병든 나이트의 이동 방법은 4가지 밖에 없어서 

    움직이려면 위나 아래로 이동을 꼭 해야하는데, 세로 길이가 1이면 이동이 불가능하다.

    방문할 수 있는 칸 = 1

 

2) n = 2일 때,

    위, 아래로 1칸씩 밖에 움직일 수 없으니 2, 3번 밖에 사용할 수 없다.

    이동 방법을 모두 사용할 수 없기 때문에 

• 이동 횟수 < 4인 경우
• 이동 횟수 >= 4인 경우

    로 나눠질 수 있다. 하지만 그렇다고 해서 풀이 방법이 달라지진 않는다.

    이동 횟수를 생각하지 않고 그림을 그려서 규칙을 찾는다면, 

    방문할 수 있는 칸 = (m + 1) // 2 라는 것을 알 수 있다.

 

    m >= 9 부터 이동 횟수가 4를 넘어가는데, 이동 방법 4개를 모두 사용할 수 없기 때문에 m = 9 부터는 모두 

    방문할 수 있는 칸 = 4가 된다.

    

3) n >= 3일 때,

    그림을 그려보면 m < 7 이면,

    이동 방법을 모두 사용할 수 없다.

    이 경우도 n = 2일 때처럼 방문할 수 있는 칸 = m 인 것은 쉽게 알아낼 수 있는데,

    이동 횟수가 4를 넘어가는 경우는 방문할 수 있는 칸 = 4가 되므로

    둘을 비교해서 작은 걸 출력해주면 된다.

 

    m >= 7이면,

    이동 방법 4가지 다 사용가능하므로 규칙만 찾아내면 된다.

    이 또한 그림을 그려보면 방문할 수 있는 칸 = m - 2 인 것을 쉽게 알아낼 수 있다.

 

n = 3 예시

---

코드

 

-파이썬

#백준 1783(병든 나이트)

n, m = map(int, input().split())  #세로, 가로
res = 0

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

print(res)

 

-자바

//백준 1783(병든 나이트)
import java.util.*;
import java.io.*;

public class Boj_1783 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());  //세로
		int m = Integer.parseInt(st.nextToken());  //가로
		int res = 0;  //이동 횟수
		
		if(n == 1) {
			res = 1;
		}
		else if(n == 2) {
			res = Math.min(4, (m + 1) / 2);
		}
		else if(n >= 3) {
			if(m < 7) {
				res = Math.min(4, m);
			}
			else {
				res = m - 2;
			}
		}
		
		System.out.println(res);
	}

}