문제

아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 <= k <= 14, 1 <= n <= 14)

출력

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

접근방법

문제를 이해하기 좀 어려웠는데, 무튼..입력으로 케이스 개수, 케이스별 층과 호가 주어지면 그걸 받아서 해당 층과 호에 살려면 필요한 숫자를 구하는 것이다. 구조체를 선언해서 층, 호, 필요한 숫자를 멤버로 갖게하고 T개의 케이스별로 관리되어야 하기 때문에 구조체 포인터로 메인문에 선언한다. T값을 입력받은대로 동적할당 및 초기화 작업을 한뒤 문제를 해결하는 함수로 구조체 포인터 주소를 전달해준다.

어려웠던 점

반복문으로 해결하기엔 뭔가 부족했다. 재귀적으로 쉽게 풀어나갈수 있을것만 같은 느낌이 들어서 수학적으로 접근해봤다.

f(0, n) = n;
f(1, n) = f(0, 1) + f(0, 2) + ... + f(0, n);
f(2, n) = f(1, 1) + f(1, 2) + ... + f(1, n);
	= f(0, 1) + (f(0, 1) + f(0, 2)) + ... (f(0, 1) +...+ f(0, n));
f(3, n) = f(2, 1) + f(2, 2) + ... + f(2, n);
			. . .
f(k , n) = f(k -1, 1) + f(k - 1, 2) + ... f(k - 1, n);
r_solution(k, n) = r_solution(k -1, 1) + ...;

k층의 n호에 살기 위해선 k-1층의 1 ~ n 호에 사는 사람들의 수를 구해야 한다. 근데 k-1층의 1호 2호 3호 ... n호에 사는 사람들의 수를 알려면 그 밑의 층 k-2층의 1호, 2호, 3호 ...n호에 사는 사람들의 수를 알아야하고, 이게 반복해서 타고 타고 내려가 0층의 1호, 2호, 3호 ... n호에 사는 사람들의 수를 알아야 한다.층은 0부터시작하고 0층의 n호는 값이 n으로 정해져 있기 때문에 브레이크 포인트와 리턴값이 명확하게 주어졌다고 볼수 있다. f(k, n) = f(k-1, 1) + f(k-1, 2) + ... f(k-1, n) 이런 형식으로 봤을 때