[백준] 2775 - 부녀회장이 될테야

#include <iostream>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;


/**
4   1 06 21 56 126 252
3	1 05 15 35 70  126
2	1 04 10 20 35  56
1	1 03 06 10 15  21
0	1 02 03 04 05  06
*/

/**
4   1 06 21 56 126 252
3	1 05           126
2	1 04
1	1 03 06 10 15  21
0	1 02 03 04 05  06
*/

using namespace std;

int GetSize(int k, int n)
{
    if (n == 1)
        return 1;
    else if (k == 0)
        return n;
    else if (n == 2)
        return k + 2;
    else if (k == 1)
        return n * (n + 1) / 2;
   
    return (GetSize(k - 1, n) + GetSize(k, n - 1));
}

int main() {
    int t, k, n;
    cin >> t;
    while (t>0)
    {
        cin >> k;
        cin >> n;
        cout<<GetSize(k, n)<<endl;
        t--;
    }
}

언어: C++

시간: 52ms

풀이:

k = 층

n = 호수 

라고 할 떄

각 층에 필요한 인원수는 (k , n-1) + (-k, n) 입니다. 재귀함수를 통해 필요한 수가 나올때 까지 반복을 돌립니다. 여기서 시간을 최대한 줄이기 위해 1 층일 떄는 가우스 공식을 이용해서 값을 바로 리턴하고 호수가 1 호면 1 , 2 호면 층 수 +2 를 리턴하도록 해서 시간을 단축하려고 시도했습니다.

 

 구하는 수에 규칙을 발견하긴 했지만, 재귀함수로 간단하게 풀 수 있었던 것을 너무 오래 고민한 것 같습니다.

 

---

다른사람 풀이입니다.

#include <stdio.h>

int apartment[15][15];
int Testcase_answer[100];
int main() {
	int Testcase;
	for (int i = 1; i <= 14; i++) {
		apartment[0][i] = i;
		apartment[i][1] = 1;
	}
	for (int a = 1; a <= 14; a++) {
		for (int b = 2; b <= 14; b++) {
			apartment[a][b] = apartment[a][b - 1] + apartment[a - 1][b];
		}
	}
	scanf("%d", &Testcase);
	for (int i = 1; i <= Testcase; i++) {
		int Floor, Digit;
		scanf("%d %d", &Floor, &Digit);
		Testcase_answer[i] = apartment[Floor][Digit];
	}
	for (int i = 1; i <= Testcase; i++) {
		printf("%d\n",Testcase_answer[i]);
	}
	return 0;

}

언어: C++ 14

시간: 0ms

풀이해설: 층 수를 입력 받기 전에 2차원 배열에 모두 저장해 놓고 입력값을 받은 후 바로 배열에 저장된 값을 출려하는 방식으로 구현하셨습니다. 처음에 2차원 배열을 사용해서 모든 층을 저장하려고 했지만 호수는 14 까지 제한이 되어 있고 층 수는 제한이 없는것으로 봐서 시도하지 않았는데 14 층 까지 제한이였다는 것을 다른사람 코드르 보면서 깨달았습니다.