백준 2775번: 부녀회장이 될테야

한 아파트가 있고, 그 아파트에는 어느 규칙이있다.
k층 n호에 살려면 바로 아래층의 1호 부터 n호까지의 사람들 수의 합만큼 같이 살아야한다는 것이다.

해당 아파트는 0층부터 시작하며 0층 n호에는 n명이 살고 있으며, 빈방이 없다고 한다면 k층 n호에는 몇명이 사는가?

 

문제를 읽고 나서 바로 이해가 되지 않아서, 표를 그려보았다.

...	...	...	...	...	...
2층	1	4	10	20	...
1층	1	3	6	10	...
0층	1	2	3	4	...
	1호	2호	3호	4호	...

 

k층 n호를 (k, n)이라고 표현했을 때, 표를 그리고나서 (k, n) = (k - 1, n) + (k, n - 1)라는 규칙을 찾을 수 있었다.

0층일 때(k == 0), n호에 사는 사람은 n명이라는 것과,

각 층의 1호는(n == 1) 무조건 1명이 산다는 것을 이용해서 재귀함수를 만들어 문제를 풀었다.

 

아래는 해당 문제의 코드이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String[] args) throws IOException {
	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	   int T = Integer.parseInt(br.readLine());
	   for (int i = 0; i < T; i++) {
	       int k = Integer.parseInt(br.readLine());
	       int n = Integer.parseInt(br.readLine());
	       bw.write(room(k, n) + "\n");
	       bw.flush();
	    }
	    bw.close();
	    br.close();
	    
	}
	
	public static int room(int k, int n) {
	    if (n == 1) return 1;
	    if (k == 0) return n;
	    return room(k-1, n) + room(k, n-1);
	}
}