백준 1783 : 병든 나이트

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

1. 접근

• 처음에는 직접 함수를 구현하려고 했지만, n과 m의 범위가 엄청나게 큰 것을 보고 다른 방법을 고안하게 되었다.

• 이때, 가로로는 오른쪽밖에 못가지만, 세로는 비교적 자유롭게 움직일 수 있다는 것을 알았다.
  => 즉, 세로가 3만 되더라도 위아래로 왔다갔다하면서 무한 이동을 할 수 있다.
  => 가로도 1234번 이동을 모두 끝냈다고하면 가로를 1밖에 안쓰는 이동방법만을 쓰면서 이동하면 최대한 많이 이동할 수 있다 !!
  => 세로는 3부터, 가로는 7(1234번을 모두 끝냈을때의 가로길이)부터는 가로2짜리를 2번 움직이고나면 그뒤로는 가로1짜리만 쓰면 된다! #1

• 이 외에 세로가 3보다 작은 경우를 분석해보자.
  => 세로가 1이면 아무곳도 갈 수 없다. #2
  (가로가 1이어도 마찬가지지만 그 경우는 다른 경우랑 합쳐서 계산가능)
  => 세로가 2면, 가로 2짜리만 계속 쓰기 때문에 가로를 2만큼 나눈 값만큼만 이동할 수 있는데, 최대 4번까지밖에 이동할 수 없다. #3
  (23번만 이용한 이동방법인데, 횟수 4번이 넘어가면 4가지 방법을 모두 써야하기때문)

• 마지막으로, 4번 방법을 모두 사용할 수 없는, 가로가 7보다 작은 경우도 비슷하다.
  => 가로 1칸짜리만 계속 사용하게되는데 이때도 최대 4번까지밖에 이동할 수 없다. #4

2. 나의 풀이

위에 길게 설명한 것을 간단하게 코드로 짤 수 있다.

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

int n, m;

int main() {
	
	cin >> n >> m;
	
	if (n == 1) { cout << 1 << "\n"; } //#2
	else if (n==2) { //오른쪽 2칸만 가능 //#3
		cout << min(4, (m + 1) / 2);
	}
	else if (m<=6){ //모든 방법 이용 불가능,4번이 넘더라도 4번까지만 이동 #4
		cout << min(4, m);
	}
	else { //2만큼 2번 움직이고 나머지는 다 1칸씩만 이동 #1
		cout << m - 2 << "\n"; 
	}
	return 0;
}

그리드는 어렵게 풀 생각 말고 간단하게 풀려고 하는게 좋은 것 같다.
설마 되겠나 하고 코드를 짰는데 60퍼, 96퍼까지 정답이 나와서 놀랐음...