백준 1010번 Combination

문제 출처 : https://www.acmicpc.net/problem/1010

문제 접근 과정

순서	내용
1	항상 N<=M 이다
2	중복이 허용 되지 않는다.
3	M개 중에서 중복을 허용하지 않고, N개를 뽑으면 되지않을까?
4	파스칼 법칙을 이용하여 dp 테이블을 초기화하여 각 Test Case에서 입력된 N,M값을 기준으로 결과를 출력하자.

What is Combination? 조합이란 무엇인가?

출처 : 나무위키

출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=lty2242&logNo=221091097459

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int T, n, m;
    static int [][] dp = new int[30][30];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(br.readLine());
        initDp();
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            sb.append(dp[m][n]+"\n");
        }
        System.out.println(sb.toString());
    }

    static void initDp() {
        //nCr 중 r == 0 이거나 n ==r 이면 경우의 수는 1
        for (int i = 0; i < 30; i++) {
            dp[i][0]=1;
            dp[i][i]=1;
        }
        for (int i = 2; i < 30; i++) {
            for (int j = 1; j < 30; j++) {
                dp[i][j]= dp[i-1][j-1]+dp[i-1][j];
            }
        }
    }
}

소스코드에 대한 부연 설명

1. Combination의 성질을 이용하여 n==r일 때, r==0일 때 1로 초기화 해둔다.
2. 그리고 BottomUp 방식으로 memozation하며 dp 테이블을 초기화한다.
3. 각 Test Case에 입력받은 n, m을 이용하여 Comb 결과를 출력한다.