C++ / 백준 / 1783 / 병든 나이트

문제

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

1783번: 병든 나이트

문제풀이

1. 처음 위치한 곳도 방문한 칸에 포함한다.

2. 이동 횟수가 3번 이하이면 네 가지 규칙 중에 마음대로 써서 움직일 수 있다.

3. 4번 이상일 경우는 네 가지 규칙을 모두 최소 한 번씩 썼으면 그 뒤로는 맘대로 골라 움직일 수 있다.

4. 4번 이상이고 네 가지 규칙 중 안 쓴 것이 있으면 규칙을 지켜야 한다.

 

N=1이면 현재 위치한 칸 말고는 갈 수 있는 칸이 없으므로 1이다.

N=2이면 2, 3번 규칙만 사용할 수 있으므로 가로 칸에 따라 답이 달라지고,

가로 칸이 커도 1, 4번 규칙을 사용하지 못하므로 최대 칸은 4칸이 된다.

N=3부터 가로 칸만 7칸 이상이면 모든 규칙을 한 번씩 쓸 수 있다.

O

O

O

O

O

7칸일 경우 오른쪽 한 칸, 한 칸, 두 칸, 두 칸이다.

7칸일 때 5칸을 방문할 수 있고 이 이후로는 오른쪽으로 한 칸씩 가는 경우가 가장 많은 칸을 갈 수 있는 경우이므로

가로 칸-2이 답이 된다.

 

코드

#include <iostream>
using namespace std;

int main() {	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N = 0, M = 0;
	cin >> N >> M;

	if (N == 1) cout << 1;
	else if (N == 2) {
		if (M < 7)	cout << (M + 1) / 2;
		else cout << 4;
	}
	else {
		if (M <= 4) cout << M;
		else if (M >= 7) cout << M - 2;
		else cout << 4;
	}
}