[BOJ] #1010 다리놓기

시간 제한	메모리 제한	정답 비율
2 초	128 MB	47.942%

 

1010번: 다리 놓기

 

방법

다리 놓기

'dp[i][j]는 서쪽에 i 개의 점이 있고, 동쪽에 j 개의 점이 있다고 했을 때 놓을 수 있는 다리의 수' 라고 정의를 해보았다.그리고 그림을 그려봤는데, 같은 i개의 점일 때는 j값에 따라 같은 모습의 다리들이 반복되는 것을 볼 수 있었고

왼쪽 상단에 보이듯이 표를 채워보니 아래와 같은 규칙을 찾아낼 수 있었다.

dp 배열

그래서 식을 세워보면 이렇게 된다.

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

 

메모리	시간
1124 KB	0 ms

#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
int t, n, m, dp[55][35];
int main(){
    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++) {
            if (i == j)dp[i][j] = 1;
            else {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
            }
        }
    }
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &m);
        printf("%d\n", dp[n][m]);
    }
    
    return 0;
}