[백준]1010. 다리 놓기 (java, python)

링크

다리 놓기

문제 분석

• 중복되지 않게 M개에서 N개를 선택해야 함 -> 조합!! m C n

  

• 위 공식을 사용할 수도 있지만 DP를 이용해서 해결해보았습니다

nCr = n-1Cr-1 + n-1Cr

• python3.8이상이라면 math.comb 메서드를 이용할 수 있습니다

코드

JAVA

import java.util.Arrays;
import java.util.Scanner;

public class Q1010 {
    static int n, m;
    static int[][] cache;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for(int t = 1; t <= tc; t++) {
            n = sc.nextInt();
            m = sc.nextInt();
            cache = new int[m + 1][n + 1];
            for(int i = 0; i <= m; i++)
                Arrays.fill(cache[i], -1);
            System.out.println(solve(m, n));
        }
    }

    public static int solve(int n, int r) {
        if(n == r || r == 0) return 1;
        int ret = cache[n][r];
        if(ret != -1) return ret;
        return cache[n][r] = solve(n - 1, r - 1) + solve(n - 1, r);
    }
}

PYTHON

import math

for _ in range(int(input())):
    n, m = map(int, input().split())
    print(math.comb(m, n))