문제
https://www.acmicpc.net/problem/1010
문제해설
n개의 점과 m개의 점이 강을 사이에 두고 있다.
n개의 점에서 m개의 점으로 다리를 놓으려고 하는데
다리는 한 점당 하나씩이고 다리가 교차하면 안된다.
이 때 만들 수 있는 다리의 최대 개수를 구하는 문제이다.
문제풀이
하나씩 그려보다보면 힌트를 찾을 수 있다.
dp[n][m] = n개와 m개의 점 사이의 다리를 만들 수 있는 경우의 수
dp[1][1] = 1
dp[1][2] = 2
dp[1][x] = x
라는 것은 알 수 있다.
그렇다면 dp[2][4]는 어떻게 될까?
2개의 점에서 가장 위 점이 4개중 가장 위 점으로 간다면
남은 한 점에서 갈 수 있는 경우의 수는 dp[1][3]과 같아진다.
그럼 가장 위의 점이 위에서 2번째 점으로 간다면 dp[1][2]와 같다.
마지막으로 위에서 3번째 점으로 간다면 dp[1][1]과 같다.
이제 감이 올텐데
dp[x][y] = dp[x-1][y-1] + dp[x-1][y-2] + ... + dp[x-1][x-1]
이라는 점화식이 만들어진다.
점화식에 맞게 코딩해주면 된다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<algorithm>
#include<vector>
#include<limits>
using namespace std;
int dp[31][31];
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
for (int i = 1; i <= 30; i++)
dp[1][i] = i;
for (int i = 2; i <= 30; i++) {
for (int j = i; j <= 30; j++) {
for (int k = j - 1; k >= 1; k--) {
dp[i][j] += dp[i - 1][k];
}
}
}
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
cout << dp[n][m] << "\n";
}
return 0;
}