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

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

코드설명

재귀함수(Recursive Function)을 활용합니다.

 

 

• 기본 조건:
  • r == 0인 경우: 아이템을 하나도 선택하지 않는 경우이므로 1을 반환합니다.
  • n == r인 경우: 모든 아이템을 선택하는 경우이므로 1을 반환합니다.
• 캐시 사용:
  • 이미 계산된 값이 cache 배열에 저장되어 있는 경우, 해당 값을 반환합니다.
• 점화식 적용:
  • 기본 조건에 해당하지 않는 경우, 점화식 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)을 사용하여 재귀적으로 값을 계산하고, 그 결과를 cache 배열에 저장합니다.
  • 결과를 MOD로 나눈 나머지를 저장하여 오버플로우를 방지합니다.

 

코드

재귀함수를 활용할경우

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, K; 
	public static int answer = 0;
	public static int MOD = 10007;
	public static int[][] cache;
	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());
		cache = new int[N+1][N+1];
		for(int i=0;i<N+1;i++) {
			Arrays.fill(cache[i], -1);
		}
		System.out.println(bino(N, K) % MOD);
	}
	
	public static int bino(int n, int r) {
		//아무 아이템을 선택하지 않을경우, 모든 아이템을 선택할경우는 1가지 경우밖에 없습니다.
		if(r == 0 || n == r) {
			return 1;
		}
		if(cache[n][r] != -1) {
			return cache[n][r];
		}
		return cache[n][r] = bino(n-1, r) % MOD + bino(n-1, r-1) % MOD;
	}
	
}

 

재귀함수를 사용할경우 2

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static int[][] map;
	static int[][] cache;
	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());
		M = Integer.parseInt(st.nextToken());
		cache = new int[N + 1][N + 1];
		for(int i=0;i<N+1;i++) {
			Arrays.fill(cache[i], -1);
		}
		
		System.out.println(binomialCoefficient(N, M));
	}
	
	static int binomialCoefficient(int n, int r) {
		if(n == r || r == 0) return 1;
		
		if(cache[n][r] != -1) return cache[n][r];
		int ret = 0;
		ret = ( binomialCoefficient(n - 1, r - 1) + binomialCoefficient(n - 1, r) ) % 10007;
		return cache[n][r] = ret % 10007;
	}
	
}

 

bino[][] 배열을 활용하여 진행할경우

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 MOD = 10007;
	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] % MOD);
	}
	
	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] % MOD + bino[i-1][j] % MOD;
			}
		}
		
	}
	
}