2775: 부녀회장이 될테야

• toc {:toc}

문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

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

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

입력

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

출력

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

제한

• 1 ≤ k, n ≤ 14

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

사고과정

첫 생각은 수학적으로 접근해야 한다는 것이었다. 규칙을 찾고자 노력했고 숫자를 그려가면서 생각했다. 표를 그려가면서 접근했는데 규칙이 보일 듯 말 듯 하며 잘 찾아지지 않았다. 이에 동기에게 질문하고 규칙을 찾으려 노력하다 보니 조합으로 문제를 풀 수 있다는 것을 깨달았다.

이에 조합으로 나타내어 풀었지만…

결과는 시간초과였다. 팩토리얼을 계속해서 돌리는데 제한을 두었더라도 많은 횟수를 돌려야 하기 때문에 시간초과가 뜬 것 같다.

#include <iostream>
 
using namespace std;
 
int factorial(int num);
 
int main()
{
	int testC, k, n, livingN;
	cin >> testC;
	for(int i=0; i<testC; i++)
	{
		cin >> k >> n;
		livingN = factorial(k+n)/(factorial(k+1)*factorial(n-1));
		cout << livingN << endl;
	}
 
	return 0;
}
 
int factorial(int num)
{
	if(num == 1)
		return 1;
	else
	{
		return num*factorial(num-1);
	}
}

이후 전혀 감을 잡지 못하겠어서 다른 사람들의 풀이를 찾아봤는데 재귀함수로 풀이할 수 있었다. 재귀함수가 의미하는 바는 결국 1층의 3호 사람의 수를 알고 싶을 때 1층 2호의 사람 + 0층 3호의 사람 ⇒ 1층 3호의 사람 수 인 것이었다.

문제를 풀이할 때 많은 문제를 풀지 않아서 인지, 혹은 방법을 모르는 것인지 잘 모르겠지만 확실한 것은 문제를 풀이할 때 여러 방법을 사용해보지 않는다는 것이 내 단점인 것 같다. 한 가지 문제를 풀 때 적어도 두 가지 방법은 생각해보도록 노력해보자.

#include <iostream>
 
using namespace std;
 
int getNum(int k, int n)
{
	if(n == 1)
		return 1;
	if(k == 0)
	{
		return n;
	}
	else
	{
		return getNum(k-1, n)+getNum(k, n-1);
	}
}
 
int main()
{
	int testC, k, n, livingN;
	cin >> testC;
	for(int i=0; i<testC; i++)
	{
		cin >> k >> n;
		livingN = getNum(k, n);
		cout << livingN << endl;
	}
 
	return 0;
}