[BAEKJOON] 2775번 부녀회장이 될테야

---

아래 표를 보면 규칙이 보이면 문제 해결 끝이다.

0층의 경우 i호에 i명이 산다고 했으니 1호에 1명, 2호에 2명 , ... , 가장 끝 방(∵ n≤14)인 14호에 14명이 거주 중일 것이다.

0층의 바로 윗 층인 1층을 보자.

1층의 1호는 0층의 1호부터 1호까지 합 즉, 1명 거주

1층의 2호는 0층의 1호부터 2호까지 합 즉, 3명 거주

1층의 3호는 0층의 1호부터 3호까지 합 즉, 6명 거주 중이다.

규칙이 보이지 않는가?

모든 층의 1호는 모두 1명이 거주할 것이고,

arr[1층][2호] = arr[0층][2호] + arr[1층][1호]

arr[1층][3호] = arr[0층][3호] + arr[1층][2호], ...

 

아래와 같은 규칙이 나타난다.

arr[층][호수] = arr[층-1][호수] + arr[층][호수-1]

 

0층의 모든 호수와 각 층마다 1호에 1명이 거주한다는 사실은 누구나 알 수 있는 사실이니 초기화해보자.

그리고 나머지 13*13 칸은 반복문으로 쉽게 채울 수 있다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		int[][] arr = new int[15][15];
		for(int i=0; i<15; i++) {
			arr[i][1] = 1;
			arr[0][i] = i;
		}
		
		for(int i=1; i<15; i++) {
			for(int j=2; j<15; j++)
				arr[i][j] = arr[i][j-1] + arr[i-1][j];
		}
		for(int tc = 0; tc<TC; tc++) {
			int k = Integer.parseInt(br.readLine());
			int n = Integer.parseInt(br.readLine());
			
			System.out.println(arr[k][n]);
		}
	}
}

[출처]

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

2775번: 부녀회장이 될테야