[백준 1011] 다리 놓기

문제 : 다리 놓기

---

문제 설명 : 강 서쪽에서 강 동쪽으로 다리를 놓으려고 한다. 

다리는 서쪽에는 N개의 사이트, 동쪽에는 M개의 사이트가 있다. (N <= M)

다리를 최대한 많이 지으려고 한다. (단, 다리끼리 겹칠수 없다.)

처음에 문제가 복잡한 것 같지만, 쉽게 생각하면 쉽게 풀리는 문제다. 

(강 서쪽에서 전체 N개의 사이트와 M개의 사이트를 잇는 문제이다.) = (M개의 사이트에서 N개를 고르는 문제.)

즉, mCn 조합문제이다. 

조합문제는 동적 계획법에서 주로 다루는 문제이다. 

---

#include <iostream>

#include <memory.h>

#define MAX 31

using namespace std;

int dp[MAX][MAX];

int comb(int n, int r) {

for (int i = 0; i <= n; i++) {

for (int j = 0; j <= r; j++) {

if (i == j || j == 0)

dp[i][j] = 1;

else

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

}

}

return dp[n][r];

}

int main() {

int T;

cin >> T;

for (int testCase = 1; testCase <= T; testCase++) {

int n, r;

cin >> r >> n;

memset(dp, 0, sizeof(dp));

cout << comb(n, r) << endl;

}

return 0;

}

---

회고. 

쉽지않네.