[1010]다리 놓기(C++)/DP

1. 문제

2. 접근 방식

1) DP

1) 항상 n개의 다리를 만들어야 한다.

•   1번째 다리의 동쪽 사이트 번호는 1이상 (M - N + 1 )이하 

•   n번째 다리의 동쪽 사이트 번호는 N이상 M이하 

•  i번째 다리의 동쪽 사이트 번호는 i 이상 (M - N + i ) 이하

2) (i번째 다리의 동쪽 사이트 번호) > (i-1번째 다리의 동쪽 사이트 번호) 

 

3) 1과 2를 합쳐보면 i번째 다리를 만들 때 고려해야 하는 것 :"i-1번째 다리를 만들 때 몇 번 사이트를 선택했는가"임을 알 수 있다. 직전에 몇 번 사이트를 선택했는지를 알면 내가 현재 선택할 수 있는 다리의 개수를 알 수 있기 때문이다. 

따라서 "현재 나는 몇 개의 다리 중 하나를 고를 수 있는가" = "직전에 몇 번 사이트를 선택했는가" 로 이해할 수 있다.  N번째 다리를 만들 때 만들 수 있는 경우의 수는 N-1번째에 선택한 사이트들의 합으로 구할 수 있다.  

 

 

4) dp[N][M] = 서쪽에 N,동쪽에 M개가 있을 때 만들 수 있는 경우의 수 = N-1번째 다리 만들 때, 올 수 있는 사이트 리스트 중 첫번째를 선택한 경우(N-1번을 선택한 경우) + N-1번째 다리 만들 때, 올 수 있는 사이트 리스트 중  2번째를 선택한 경우(N번을 선택한 경우) + ... + N-1번째 다리 만들 때, 올 수 있는 사이트 리스트 중 M-1번째 사이트를 선택한 경우(M-1번을 선택한 경우)

   dp[N][M] = dp[N-1][1] + dp[N-1][2] + ... + dp[N-1][M-1]

 

5)초기 값: dp[1][i] = i

 

2) M 기준에서 보기

-M개 중 다리를 놓을 N개를 고르면 순서는 알아서 정해지므로 mCn으로 풀 수 있다. mCn = (m-1)C(n-1) + (m-1)Cn이며 n == 0 이거나 m == n 일 때 return 1을 수행한다.

 

3. 배운 점

1) dp에서 중요한건 직전 항과의 관계를 찾는 것. 수식적으로 i번째 경우의 수는 "f(i)" 이다!라고 딱 값이 나오도록 생각하려다 보면 규칙을 찾기도 어려워 지고 점화식을 구하는 것도 어려워 진다. 재정의 하는 법 연습할 것.

 

2) "N번,M번째 경우의 수를 구하고 싶다" = "N개,M개가 남아 있을 때 경우의 수를 구하고 싶다." 라고 생각해 보기

 

3) N,M이 주어지면 dp[n][m] 구하는 것을 떠올려 보자 => dp[n][m]으로 만들 수 있는 것은? 서쪽에 n, 동쪽에 m개 있을 때 만들 수 있는 경우의 수! 즉, "개수 기준"으로 접근해서 점화식을 찾아보도록 하자. 

 

4) dp로 풀 떄, v의 초기값을 -1로 했더니 경우의 수 계산 시 -1이 계산된다. -> 아직 해당 문제를 완벽하게 이해하지 못해서.. 왜인지는 잘 모르겠지만 일단 경우의 수 구할 땐 0으로 초기화 하자

4. 코드

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

//dp로 풀 때(bottom-up)
int solution(int n,int m) {
	vector<vector<int>> v(n+1,vector<int>(m+1,0));
	for(int i=1;i<=m;i++)	
		v[1][i] = i;
	
	for(int i=2;i<=n;i++) {
		for(int j=i;j<=m;j++) {
			if(j == i) {
				v[i][j] = 1;
				continue;
				}
			 for(int k=i-1; k<=j-1;k++) 
				v[i][j] += v[i-1][k];
		}
	}

	return v[n][m];
}

//조합으로 풀 때 

int go(int m, int n, vector<vector<int> > &v) {
	if( n == 0 || m == n ) return 1;
	if( v[m][n]) return v[m][n];
	return v[m][n] = go(m-1,n-1,v) + go(m-1,n,v);
}
int solution_2(int n,int m) {
	vector<vector<int> > v(n,vector<int>(m,0));
	return go(m,n,v);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	int n,m,T;
	cin >> T;
	while(T--) {
	cin >> n >> m;
	cout <<solution(n,m)<<"\n";
	}
	return 0;
}