[백준] 1010 (실버5) 조합

https://www.acmicpc.net/problem/1010

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int N, M, count;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for(int i=0;i<T;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            //M C N 결과 출력
            count = 0; // 초기화
            comb(0,0);
            bw.write(String.valueOf(count));
            bw.write("\n");
        }

        bw.flush();
        br.close();
        bw.close();
    }

    static void comb(int m, int n){
        if(n==N){
            count++;
            return;
        }

        if(m == M) return;

        comb(m+1, n+1);
        comb(m+1, n);
    }
}

=> 시간 초과
1. 조합 식의 계산 값만 나오게 변경

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for(int i=0;i<T;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            int count = comb2(M,N);
            bw.write(String.valueOf(count));
            bw.write("\n");
        }

        bw.flush();
        br.close();
        bw.close();
    }

    static int comb2(int m, int n){
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        if (n > m - n) n = m - n;
        int count = 1;
        for (int i = 1; i <= n; i++) {
            // n ~ n-r+1의 곱 / n-r-1 ~ 1의 곱
            count = count * (m - n + i) / i; // 매 스텝마다 나눗셈으로 정수 유지
        }
        return count;
    }
}

2. 파스칼의 삼각형 만들어서 이항계수 값 선택하기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
    static int T, N, M;
    static int[][] memoi;
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            
            // 초기화
            memoi = new int[M + 1][M + 1];
            memoi[0][0] = 1;
            
            for (int i = 1; i <= M; i++) { // 행
                for (int j = 0; j <= i; j++) { // 열
                    // 맨 앞, 맨 뒤
                    if( j == 0 || j == i ) {
                        memoi[i][j] = 1;
                        continue;
                    }
                    memoi[i][j] = memoi[i-1][j-1] + memoi[i-1][j]; // 이전 행 (i-1) 의 j 기준 왼쪽, 오른쪽
                }
            }
            
            System.out.println(memoi[M][N]);
        }
    }
}

3. 재귀 호출

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 파스칼 삼각형을 이용 X, 재귀 호출 이용, 메모이제이션 기법
// 메모리 사용이 적다
// 재귀호출 부담
public class Main {
    static int T, N, M;
    static int[][] memoi;
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            
            // 초기화
            memoi = new int[M + 1][N + 1];
            
            System.out.println(comb(M, N));
        }
    }
    // nCr 의 수
    // 반복적인 재귀호출의 과정에서 memoi 배열 활용
    static int comb(int n, int r) {
        if( n == r || r == 0 ) {
            return memoi[n][r] = 1;
        }
        
        if( memoi[n][r] > 0 ) return memoi[n][r];
        
        // nCr
        return memoi[n][r] = comb(n-1, r-1) + comb(n-1, r);
    }
}