2775)부녀회장이 될테야

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

k층 n번째에 들어갈 사람의 수는 다음처럼 구할 수 있다.

예를들어 1층 4호에 입주할 사람의 수는 아래 그림과 같다.

0층 1호부터 4호까지 입주한 사람들의 합이다.

그렇다면 2층 5호에 입주할 사람의 수는?

위 그림처럼 1층 1호~ 1층 5호까지 합을 구해야 한다.

그리고 1층 의 각 호실에 입주할 사람의 수를 구해야 한다.

문제를 해결하기 위해 자기 반복 구조를 사용해야 해서 재귀 함수를 작성했다.

#include<stdio.h>
 
int calculate(int k, int n) {
    int sum = 0;
 
    if (k == 0) return n;
    else {
        for (int i = 1; i <= n; i++) {
            sum+=calculate(k - 1, i);
        }
        return sum;
    }
}
 
int main() {
    int N;
    int n, k;
    int num;
 
    scanf("%d",&N);
    for (int i = 0; i < N;i++) {
        scanf("%d",&k);
        scanf("%d",&n);
 
        num = calculate(k,n);
        printf("%d\n",num);
    }
 
    return 0;
}

 

재귀 함수로 이 문제를 풀어도 크게 문제가 없다.

그러나 테스트 입력이 여러 번 있기 때문에 이미 구했던 값을 다시 구해야 하는 경우가 잦아진다.

차라리 미리 모든 값들을 구해서 테이블로 만든 후 각 테이블에 인덱싱하는 편이 빠를 것이다.

위 코드를 동적 프로그래밍으로 고치면 아래와 같다.

#include<stdio.h>
 
int main() {
    int N;
    int n, k;
    int num;
    int apart[15][15];
 
    for (int j = 0; j < 15;j++) {
        apart[0][j] = j;
    }
    for (int i = 0; i < 15;i++) {
        apart[i][0] = 0;
        apart[i][1] = 1;
    }
 
    for (int i = 1; i < 15;i++) {
        for (int j = 2; j < 15;j++) {
            apart[i][j] = apart[i - 1][j] + apart[i][j - 1];
        }
    }
 
    scanf("%d",&N);
    for (int i = 0; i < N;i++) {
        scanf("%d",&k);
        scanf("%d",&n);
 
        num = apart[k][n];
        printf("%d\n",num);
    }
 
    return 0;
}

위 그림은 동적 프로그래밍을 통해 미리 테이블의 값들을 채운다.

(i,j)의 값은 (i,j-1)의 값과 (i-1,j)의 값의 합이다. (i,j-1)은 (i-1,1)의 값부터 (i-1,j-1)의 값까지 합이기 때문이다.

이렇게 테이블을 만들고 테이블에 접근하면 보다 빠르게 문제를 풀 수 있다.