[BaekJoon] 11050번 이항 계수1 문제 풀이 (Success)

11050번: 이항 계수 1

 

☕Language: Java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.valueOf(st.nextToken());
        int b = Integer.valueOf(st.nextToken());
 
        int top = 1;
        int btm = 1;
        
        int cnt = b;
        while(cnt-->0) {
            top *= a;
            a--;
            btm *= b;
            b--;
        }
        
        bw.write((top/btm)+"");
 
        bw.flush();
        bw.close();
 
    }
}
 

🤔 해설

* 이항계수: n개의 원소에서 k개의 원소를 뽑아내는 경우의 수

nCk = n! / (n-k)! * k!

1. while(cnt-->0){ ... }

    - 분모의 개수는 분자의 시작값과 동일하므로 cnt동안 반복

 

😮 이 외의 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(st.nextToken());
        int K = Integer.valueOf(st.nextToken());
 
        int result = factorial(N) / (factorial(N - K) * factorial(K));
 
        bw.write(result + "");
 
        bw.flush();
        bw.close();
 
    }
 
    public static int factorial(int i) {
        if (i <= 1)
            return 1;
 
        return i * factorial(i - 1);
    }
}
 

1. public static int factorial(int i) { ... }

    - 재귀 호출을 통한 팩토리얼 구현

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(st.nextToken());
        int K = Integer.valueOf(st.nextToken());
 
        bw.write(pascalsT(N, K) + "");
 
        bw.flush();
        bw.close();
 
    }
 
    public static int pascalsT(int N, int K) {
        if(N==K | K==0)
            return 1;
        
        return pascalsT(N-1, K-1) + pascalsT(N-1, K);
    }
}
 

* 파스칼의 삼각형 법칙

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

n번째 행의 r번째 수 (nCr)는 (n-1)번째 행의 (r-1)번째 수 (n-1Cr-1)과 (n-1)번째 행의 r번째 수 (n-1Cr)의 합과 같다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    static int[][] dp;
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(st.nextToken());
        int K = Integer.valueOf(st.nextToken());
 
        dp = new int[N + 1][K + 1];
 
        bw.write(pascalsT(N, K) + "");
 
        bw.flush();
        bw.close();
 
    }
 
    public static int pascalsT(int N, int K) {
 
        // Memoization
        if (dp[N][K] > 0)
            return dp[N][K];
 
        if (N == K | K == 0)
            return dp[N][K] = 1;
 
        return dp[N][K] = pascalsT(N - 1, K - 1) + pascalsT(N - 1, K);
    }
}
 

* Memoization 활용

Memoization은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

[백준] 11050번 : 이항 계수 1 - JAVA [자바]