[C++] 백준 2775

백준의 2775번 문제 부녀회장이 될테야 문제이다.

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

2775번: 부녀회장이 될테야

---

 < 문제 >

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

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

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

 

 < 예제 >

문제는 간단하다.

아파트에 거주하기 위해서는 인원수를 맞춰야 하는데 이는 아래층의 인원수만큼 들어와야된다.

간단히 그림을 통해 설명하자면

우선 간단히 필요한 인원수를 적어보았다.

표를 보고 설명하자면 3층 3호실에 15라고 적어놓았는데 만약 3층 3호실에 입주하고 싶다고 한다면 

그러기 위해서는 2층의 1호실(1) 2호실(4) 3호실(10)의 인원을 전부 합한 만큼 인원이 들어와야 된다는 것이다.

또다른 예를 들자면 3층 8호실에 들어가고자 한다면 2층 1호실 ~ 8호실의 인원을 전부 합한만큼 입주해야 되는 것이다.

실로 정신나간 아파트라고 볼 수 있다.

 

아무튼 설명은 이정도로 마치고 코드를 살펴보도록 하자

 

#include <iostream>
#include <string>
using namespace std;

int total_people(int k, int n) {
	if (n == 1)
		return 1;

	if (k == 0)
		return n;

	return (total_people(k - 1, n) + total_people(k, n - 1));
}

int main() {

	int t;
	cin >> t;

	int k, n;
	for (int i = 0; i < t; ++i) {
		cin >> k;
		cin >> n;
		cout << total_people(k, n) << endl;
	}
}

이 문제에서는 잘 보면 규칙을 발견할 수 있다.

3층 5호실에 들어가기 위해서는 2층의 1호실 ~ 5호실을 전부 합한만큼 입주해야 하는데

잘 보면 3층 4호실 + 2층 5호실의 값과 동일한 것을 알 수 있다.

이 점을 활용하기 위해여 재귀함수를 사용하였다.

 

int total_people(int k, int n) {
	if (n == 1)
		return 1;

	if (k == 0)
		return n;

	return (total_people(k - 1, n) + total_people(k, n - 1));
}

문제에서 0층의 경우 호실 번호만큼 인원이 들어간다고 가정하였기 때문에 return n을 해주었고

1호실의 경우 전부 1이기 떄문에 return 1을 해주었다.

 

그리고 

return (total_people(k - 1, n) + total_people(k, n - 1));

여기서는 아래층 + 옆집 을 리턴하게 해두었다.

 

규칙을 찾고 재귀함수를 이용한다면 생각보다 간단히 풀리는 문제이다.