(JAVA) 백준 11050번 : 이항 계수 1

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

11050번: 이항 계수 1

 

nCr 을 구하는 문제인데 첫 풀이로 노가다 방식으로 진행해봤다.

이번 문제와 같이 수의 범위가 크지 않다면 문제가 없지만 비효율적이고 코드도 예쁘지 않다고 생각하여

총 3가지 풀이로 진행해봤다.

 

가장 기본적인 풀이 (row)

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

public class Main 
{
	public static int T = 0;
	public static void main(String[] args) throws IOException 
	{	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		
		int G = 1;
		int D = 1;

		for(int i =0 ;i<B;i++)
		{
			G *= (A-i);
		}

		while(B > 0)
		{
			D *= B;
			B--;
		}
		System.out.println(G/D);
	
	}
}

 

Factorial

nCr = n! / (n-k)! * k! 임을 이용

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	public static void main(String[] args) throws IOException 
    {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
 
		System.out.println(factorial(N) / (factorial(N - K) * factorial(K)));
	}
 
	static int factorial(int N) 
    {
		// factorial(0) == 1 이다. 
		if (N <= 1)	{
			return 1;
		}
		return N * factorial(N - 1);
	}
}

 

BC 방식

 💡 동적계획법 ,DP(Dynamic Programming)

: 어떤 주어진 문제를 작은 문제로 쪼개서 풀어나감에 있어 반복

반복되는 문제는 한 번만 푼다. 즉, 이미 풀렸던 값을 재활용함을 의미.

그리고 이러한 재활용, 즉 이미 풀린 하위 문제를 다시 풀지 않고 재활용 하는 것을

메모이제이션(Memoization) 이라고 한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	static int[][] dp;
 
	public static void main(String[] args) throws IOException 
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
 
		dp = new int[N + 1][K + 1];
 
		System.out.println(BC(N, K));
 
	}
 
	static int BC(int n, int k) 
	{
		// 이미 풀었던 sub문제일 경우 값을 재활용
		if (dp[n][k] > 0) 
		{
			return dp[n][k];
		}
 
		// 2번 성질
		if (k == 0 || n == k) 
		{
			return dp[n][k] = 1;
		}
 
		// 1번 성질, 2번 성질을 만족할 때까지 줄여가는 방식
		return dp[n][k] = BC(n - 1, k - 1) + BC(n - 1, k);
	}
}

 

참고

https://st-lab.tistory.com/159#%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98