[백준] 1783-병든 나이트(C++)

문제링크: https://www.acmicpc.net/problem/1783

1783번: 병든 나이트

 

문제의 규칙입니다.

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

그리고 4회이상 이동시 4가지이동을 포함해야한다는 규칙이 있습니다.

 

 

만약 n이 1이라면, m값과 관계없이 이동이 불가하기 때문에 1입니다.

 

만약 n이 2이라면, 2번과 3번 이동이 가능해집니다.

올라갔다 내려갔다 하면서 이동할 수 있겠죠! 하지만  4회이상 이동시 4가지이동을 포함해야한다는 규칙때문에 3회의 이동까지만 가능합니다. (1번, 4번이동은 2칸 씩 이동해야하지만 그것이 불가능하기 때문에) 

 

만약 n이 3이상이라면, 규칙적으로 이동하게 됩니다. m이 7이상이여서 문제의 규칙 1, 2, 3, 4번 이동이 모두 가능하다면 각각 4번의 이동를 하고 그 이후부터는 1, 4번 이동만을 반복할 것입니다. (가장 많이 탐색하기 위해서)

즉, m-2번 탐색이 가능해집니다.

 

위의 3가지 규칙을 생각하면서 예외를 처리해주시면 됩니다.

 

정답코드입니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int main() {
	cin >> n >> m;
	if (n == 1) {
		cout << 1 << endl;
	}
	else if (n == 2) {
		if (m >= 7)
			cout << 4 << endl;
		else
			cout << (m + 1) / 2 << endl;
	}
	else {
		if (m >= 7) {
			cout << m - 2 << endl;
		}
		else {
			cout << min(4, m) << endl;
		}
	}
}

 

n 의 갯수마다 처리해야할 예외가 다릅니다. 

조건문들의 조건은 직접 그림을 그리며 이해해보세요.

화이팅! :)