[백준] 11050 이항 계수 1 - 재귀함수(Recursive Function) JAVA

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

코드설명

재귀함수(Recursive Function)를 사용합니다.

 

코드로직입니다.

 

• 기본 조건:
  • r == 0인 경우: 아이템을 하나도 선택하지 않는 경우이므로 1을 반환합니다.
  • n == r인 경우: 모든 아이템을 선택하는 경우이므로 1을 반환합니다.
• 점화식 적용:
  • 기본 조건에 해당하지 않는 경우, 점화식 C(n,k)=C(n−1,k)+C(n−1,k−1)C(n, k) = C(n-1, k) + C(n-1, k-1)C(n,k)=C(n−1,k)+C(n−1,k−1)를 사용하여 재귀적으로 값을 계산합니다.

코드

재귀함수를 활용한 경우

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, K; 
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		System.out.println(bino(N, K));
	}
	
	public static int bino(int n, int r) {
		//아무 아이템을 선택하지 않을경우, 모든 아이템을 선택할경우는 1가지 경우밖에 없습니다.
		if(r == 0 || n == r) {
			return 1;
		}
		return bino(n-1, r) + bino(n-1, r-1);
	}
	
}

bino[][] 2차원 배열을 활용할경우

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, K; 
	public static int answer = 0;
	public static int[][] bino;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		bino = new int[N+1][N+1];
		bino();
		System.out.println(bino[N][K]);
	}
	
	public static void bino() {
		for(int i=0; i<=N; i++) {
			for(int j=0; j<=i; j++) {
				if(j == 0 || j == i) {
					bino[i][j] = 1;
					continue;
				}
				bino[i][j] = bino[i-1][j-1] + bino[i-1][j];
			}
		}
		
	}
	
}