백준 1010

*solved.ac 기준 실버 5단계 문제

풀이)
해당 문제는 조합의 성질을 이용해서 풀어야 한다.
그러나 for문을 통해 곱셈을 진행하면 제한 시간 내에 풀지 못한다.
또한 30! 은 int 정수형 범위를 뛰어넘기 때문에 잘못된 값을 출력할 수 있다.

따라서

공식을 이용해 풀어야 한다.

N, M은 1~30 사이의 정수이므로,
int [31][31] 크기 배열 안에 해당하는 조합의 값을 삽입할 것이다.

1. 먼저 MC1 = M이므로 int[M][1] = M 이다.
2. MCN = (M-1)C(N-1) + (M-1)CN 이므로 int[M][N] = [M-1][N-1] + [M-1][N]

만약 2중for문을 통해 하나하나 계산한다면 중복되는 것도 모두 계산해야 하지만, 배열을 통해 값을 미리 저장해두면 다시 계산할 필요 없이 필요한 값을 가져오면 된다.

내 코드)

import java.util.*;
import java.io.*;

public class Backjoon1010 {
    private final static int MAX = 30;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());
        
        int[][] dp = new int[MAX + 1][MAX + 1];
            
        for (int i = 1; i <= MAX; i++) {
            dp[i][1] = i;
        }

        for (int j = 2; j <= MAX; j++) {
            for (int k = 2; k <= MAX; k++) {
                dp[j][k] = dp[j - 1][k - 1] + dp[j - 1][k];
            }
        }
        
        for (int i = 0; i < T; i++) {
            int[] input = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int n = input[1];
            int r = input[0];
            
            System.out.println(dp[n][r]);
        }
    }
}