1010번: 다리 놓기

문제 풀러가기

1010

설명

겹쳐지게 다리를 놓을 수 없고 서쪽의 사이트 개수(N개)만큼 지으려고 한다. N을 고정해 놓고 M의 값을 키우면서 경우의 수를 확인하면 dp[N][M] = dp[N][M - 1] + dp[N - 1][M -1]이라는 규칙을 발견할 수 있다.

코드

import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int t = sc.nextInt();

    for(int i = 0; i < t; i++) {
      int N = sc.nextInt();
      int M = sc.nextInt();

      int dp[][] = new int[N + 1][M + 1];

      for(int n = 2; n <= N; n++) {
        dp[n][1] = 0;
      }

      for(int m = 1; m <= M; m++) {
        dp[1][m] = m;
      }

      for(int x = 2; x <= N; x++) {
        for(int y = 2; y <= M; y++) {
          dp[x][y] = dp[x][y - 1] + dp[x - 1][y - 1];
        }
      }

      System.out.println(dp[N][M]);
    }
  }
}