BOJ 27533 따로 걸어가기

문제 링크입니다.

풀이1 : 생각하기

처음에 한 마리는 오른쪽으로, 다른 한 마리는 아래로 보내 줍니다. 이제 집에 도착할 때까지 둘은 서로 만나지 않고 각각 집 위쪽, 집 왼쪽에 도달해야 합니다.

아래쪽의 토끼가 아래쪽으로, 오른쪽의 토끼가 오른쪽으로 갑니다. 그러면 둘의 중앙을 가르는 45도 방향의 대각선을 생각했을 때, 두 토끼가 그 대각선으로부터 멀어집니다. 반대로 움직이면 대각선에 가까워지고, 둘이 같은 방향으로 움직이는 경우에는 대각선까지 그대로 함께 이동하는 꼴이 됩니다.

이 대각선에 토끼가 닿으면 두 토끼가 서로 만나게 됩니다. 그러지 않기 위해서는 첫 이동과 마지막 이동을 제외한 이동 전반에 걸쳐 멀어지는 이동의 수가 가까워지는 이동의 수 이상이어야 하고, 최종적으로는 두 움직임의 횟수가 서로 같아야 합니다.

이거 올바른 괄호 문자열이랑 조건이 똑같습니다. 카탈란 수를 이용해 이 경우의 수를 구할 수 있음이 알려져 있고, 둘이 평행하게 이동하는 횟수는 멀어지고 가까워지는 이동의 수에 따라 자동으로 결정되니 다른 이동을 배치한 후에 그 사이에 적당히 끼워넣어 주면 됩니다. 이 작업은 중복조합 등을 잘 써서 해결할 수 있습니다.

풀이2 : 유연한 오버킬, 사고하지 않기

(1, 2), (2,1)에서 (N-1, M), (N, M-1)로 서로 겹치지 않는 경로로 보내는 경우의 수를 구하는 문제이므로, LGV Lemma를 알고 있다면 아무 생각 없이 4가지 경로의 수를 구한 뒤 바로 답을 구할 수 있습니다.

풀이1 - 코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
ll f[4234567]={1};
ll inv[4234567];

ll pw(ll n, ll r){
	ll ret = 1;
	while(r){
		if(r&1) ret = ret*n%mod;
		n = n*n%mod;
		r >>= 1;
	}
	return ret;
}

inline ll comb(int n, int r){return f[n]*inv[r]%mod*inv[n-r]%mod;}
inline ll H(int n, int r){return comb(n+r-1, r);}
inline ll catalan(int n){return pw(n+1, mod-2)*comb(2*n, n)%mod;}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int n, m; cin >> n >> m; n--; m--;
	if(n > m) swap(n, m);
	for(int i = 1; i <= n+m; i++) f[i] = f[i-1]*i%mod;
	inv[n+m] = pw(f[n+m], mod-2);
	for(int i = n+m-1; i >= 0; i--) inv[i] = inv[i+1]*(i+1)%mod;
	ll ans = 0;
	for(int i = 0; i < n; i++){
		ll tmp = catalan(i);
		tmp = tmp*comb(n+m-2-2*i, n-1-i)%mod;
		tmp = tmp*H(2*i+1, n+m-2-2*i)%mod;
		ans = (ans+tmp)%mod;
	}
	cout << ans*2%mod;
}

풀이2 - 코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
ll f[4234567]={1};
ll inv[4234567];

ll pw(ll n, ll r){
	ll ret = 1;
	while(r){
		if(r&1) ret = ret*n%mod;
		n = n*n%mod;
		r >>= 1;
	}
	return ret;
}

inline ll C(int n, int r){if(n < 0 || r < 0 || r > n) return 0; return f[n]*inv[r]%mod*inv[n-r]%mod;}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int n, m; cin >> n >> m;
	for(int i = 1; i <= n+m; i++) f[i] = f[i-1]*i%mod;
	inv[n+m] = pw(f[n+m], mod-2);
	for(int i = n+m-1; i >= 0; i--) inv[i] = inv[i+1]*(i+1)%mod;
	cout << (C(n+m-4, m-2)*C(n+m-4,m-2)%mod-C(n+m-4,m-1)*C(n+m-4,m-3)%mod+2*mod)*2%mod;
}