JArchive 프로그래밍 일기

문제 링크 

n <= m 조건을 가지고 있고,  다리를 만드는 경우의 수를 센다. 

문제 하단에 '다이나믹 프로그래밍' 이라고 힌트가 써있길래 2차원 배열로 풀 수 있었다. 

먼저 n과 m이 같은 수라면 경우의 수는 전부 1개다.  

n == 1 이면, m이 뭐든간에 경우의 수는 m개다. 

입력을 받기 전에, DP배열을 미리 채워놓는다. 

a[2][2] = 1 

a[2][3] = a[1][1] + a[1][2]

a[2][4] = a[1][1] + a[1][2] + a[1][3] 

a[i][j] = a[i-1][1] + a[i-1][1] + .... + a[i-1][j-1]

"맞았습니다" 코드 링크 

/** 다리 놓기
 * https://www.acmicpc.net/problem/1010
 * http://boj.kr/2dd342c6f44849369f678383dea56dbf
 * */
#include <bits/stdc++.h>
using namespace std;

int t, n, m;
int a[32][32];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  for(int i = 1; i <= 30; i++){
    a[i][i] = 1; a[1][i] = i;
  }
  for(int i = 2; i < 30; i++){
    for(int j = i+1; j < 30; j++){
      for(int k = 1; k < j; k++){
        a[i][j] += a[i-1][k];
      }
    }
  }
  cin >> t;
  while(t--){
    cin >> n >> m;
    cout << a[n][m] << '\n';
  }
  return 0;
}