[1010] 다리 놓기

✔ 다리 놓기

[백준 1010]

문제 분석하기

다리끼리 서로 겹쳐질 수 없기 때문에 M개의 사이트에서 N개를 뽑는 경우의 수를 구하는 조합 문제

손으로 풀어보기

1. M이 30이므로 이에 따라 DP 배열을 선언
   • D[N + 1][N + 1] = D[31][31]
2. DP 배열의 값을 초기화
   • i개 중 1개를 뽑는 경우의 수인 D[i][1] = i
   • i개 중 1개도 선택하지 않는 경우이 수인 D[i][0] = 1
   • i개 중 i개를 뽑는 경우의 수인 D[i][i] = 1
3. 점화식으로 DP 배열의 값을 채움
   • D[i][j] = D[i - 1][j] + D[i - 1][j - 1]
4.  D[M][N]의 값을 출력함

슈도코드 작성하기

T(테스트 케이스) N(서쪽) M(동쪽)
D(DP 배열)
for(i -> N만큼 반복하기) {
    D 배열 초기화하기
    D[i][1] = i
    D[i][0] = 1
    D[i][i] = 1
}
for(i -> N만큼 반복하기) {
    for(j -> i만큼 반복하기) {
        D[i][j] = D[i - 1][j] + D[i - 1][j - 1]
    }
}
for(T의 개수) {
    N와 M의 값을 입력받음
    D[M][N] 출력하기
}

코드 구현하기

/**
 * 1010) 다리_놓기
 */
public class D079_1010 {
    static int T, N, M;
    static long[][] D;

    public static void main(String[] args) {
        // D(DP 배열)
        D = new long[31][31];
        // D 배열 초기화하기
        for (int i = 0; i <= 30; i++) {
            D[i][1] = i;
            D[i][0] = 1;
            D[i][i] = 1;
        }
        for (int i = 2; i <= 30; i++) {
            // 고르는 수의 개수가 전체 개수를 넘을 수 없음
            for (int j = 1; j < i; j++) {
                // 조합 점화식
                D[i][j] = D[i - 1][j] + D[i - 1][j - 1];
            }
        }
        Scanner sc = new Scanner(System.in);
        // T(테스트 케이스)
        T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            // N(서쪽)
            N = sc.nextInt();
            // M(동쪽)
            M = sc.nextInt();
            // D[M][N] 출력하기
            System.out.println(D[M][N]);
        }
    }
}