[백준 알고리즘 2775번 문제] 부녀회장이 될테야 (C언어) #브론즈Ⅰ

브론즈Ⅰ

 

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

2775번: 부녀회장이 될테야

 

 

풀이 방법

 

입력값 k층 n호의 k와 n의 값을 각각 5층 3호로 가정했을 때 다음과 같이 나타낼 수 있었다.

5층	1	7	28
4층	1	6	21
3층	1	5	15
2층	1	4	10
1층	1	3	6
0층	1	2	3

위 표를 보았을 때 동일한 층의 (n-1)호의 사람의 수와 (k-1) 층의 동일한 호의 사람의 수의 합이 구하고자 하는 k층 n호의 사람 의 수가 됨을 알 수 있다. 즉, (k)층의 (n-1)호의 사람의 수 + (k-1) 층의 (n)호의 사람의 수 = (k) 층의 (n)호의 사람의 수가 된다.

그리고 (k)층의 (n-1)호의 사람의 수는 다시 (k-1) 층의 (n-1-1)호의 사람의 수와 (k-1-1) 층의 (n)호의 사람의 수의 합이 되므로, 재귀함수를 이용한 코드를 작성하면 풀 수 있다.

 

내 코드

 

#pragma warning(disable:4996)
#include <stdio.h>
 
int func(int k, int n);
 
int main(void) {
    
    int T, k, n, i, result = 0;
 
    scanf("%d", &T);
 
    for (i = 0; i < T; ++i) {
        scanf("%d %d", &k, &n);
        
        result = func(k, n);
        printf("%d\n", result);
    }
 
    return 0;
}
 
int func(int k, int n) {
    if (n == 0)
        return 0;
    else if (k == 0)
        return n;
    return func(k, n - 1) + func(k - 1, n);
}

 

 

느낀 점

 

다른 사람들이 작성한 코드를 보았을 때 대부분이  '(k)층의 (n-1)호의 사람의 수 + (k-1) 층의 (n)호의 사람의 수 = (k) 층의 (n)호의 사람의 수가 된다.'라는 사실을 이용했으나, 다른 이가 쓴 코드는 15x15의 배열을 만들어서 값을 모두 대입해 넣은 후 원하는 k층의 n호의 사람 수를 출력한 경우가 많았고, 나는 재귀함수를 이용해 문제를 풀었다.

15x15라는 제한이 걸려있기도 하고, T라는 테스트케이스의 횟수만큼 계산을 하기 때문에 재귀함수를 이용한 코드보단 미리 2차원배열에 값을 저장해 놓는 방법이 속도의 측면에서는 더 빠를 것 같긴 하다. 하지만 재귀함수를 이용하면 코드도 짧아지고 있어 보이니까...