[BaekJoon] 백준 2775. 부녀회장이 될테야

 

 

a, b가 주어지면 a층 b호에 사는 주민의 수를 구하는 문제

설명 생략

 

점화식을 세워서 풀었다.

 

 

d[a][b] = d[a-1][b] + d[a][b-1]

 

a층 b호에사는 주민의 숫자는 이전의 호수 즉 a층 b-1호에 사는 주민의 수와 a-b층 b호에 사는 주민의 수를 합한 것과 같습니다.

(단, 1호일 경우 a-1층의 1호에 사는 주민의 수와 같다)

 

 

재귀를 사용하여 문제를 풀었습니다.

import java.util.Scanner;

public class main {
	static int[][] d;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int test_case = scan.nextInt();
		for(int j = 1; j<=test_case; j++) {
			int n = scan.nextInt();
			int i = scan.nextInt();
			
			d = new int[n+1][i+1];
			
			for(int k = 1; k<=i; k++) {
				d[0][k] = k;
			}

			func(n, i);
			
			System.out.println(d[n][i]);
		}
	}
	
	public static int func(int n, int i) {
		if(d[n][i] != 0) {
			return d[n][i];
		}
		else {
			if(i == 1) {
				d[n][i] = func(n-1, i);
			}
			else {
				d[n][i] = func(n, i-1) + func(n-1, i);
			}
			return d[n][i];		
		}
	}
}