[백준/C++] 2775번 : 부녀회장이 될테야

문제

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

이 아파트에 거주를 하려면 조건이 있는데, “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

풀이

조금 이상한 아파트 같다.

01. 반복을 이용

호수가 최대 14호까지이므로, 15*14 이차원 배열을 생성한 후, 반복문을 통해 아파트의 주민 수를 모두 구한다.

이후 해당하는 층과 호수를 이용해 바로 출력한다. 

 

하지만 굳이 아파트의 주민 수를 모두 구할 필요는 없을 것 같아서,

int arr[15][14]에 먼저 1층의 주민 수를 넣은 후, 아래 층의 주민 수를 하나씩 더해주는 방법으로 풀었다. 

(물론 이번 문제는 제한 시간이 조금 여유롭기 때문에 아파트의 주민 수를 모두 구할 수 있다!)

#include <iostream>
using namespace std;

int main(){
    int T, K, N;
    cin >> T;
    for (int i=0; i<T; i++){
        cin >> K;
        cin >> N;
        int arr[15][14]={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
        // k층의 n호에 몇 명이 살고 있는가
        int resident;
        for (int floor=1; floor<=K; floor++){
            for (int room=0; room<N; room++){
                resident += arr[floor-1][room];
                arr[floor][room] = resident;
            }
            resident=0;
        }
        cout << arr[K][N-1] << endl;
    }
}

반복문을 한 번 더 써서 더욱 간단하게 만들 수 있다. 

for (int i = 0; i < t; i++) {
		int res[15][14] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
		cin >> k >> n;
		for (int j = 1; j <= k; j++) {
			for (int l = 0; l < n; l++) {
				for (int m = 0; m <= l; m++) {
					res[j][l] += res[j - 1][m];
				}
			}
		}
		cout << res[k][n - 1] << endl;
	}

 

02. 재귀 이용

https://aorica.tistory.com/124님의 풀이인데 간결해보여서 공유한다!

#include <iostream>

using namespace std;

int getNum(int a, int b){
  if(b == 1)
    return 1;
  if(a == 0)
    return b;
  return (getNum(a-1, b) + getNum(a, b-1));
}

int main() {
  int T, k, n;
  cin>>T;
  for(int i=0; i<T; i++){
    cin>>k>>n;
    cout<<getNum(k, n)<<'\n';
  }
}

---

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

2775번: 부녀회장이 될테야

3번만에 성공해서 기분이 좋다 희희