BOJ)2775 부녀회장이 될테야

문제: icpc.me/2775

a층 b호에 사는 주민은 a-1층의 1~b호까지의 주민의 합일때 k층n호에 사는 주민의 수를 출력하는 문제이다.

사실 k와 n의 범위가 매우 작기 때문에 그때 그때 구해줘도 TLE를 받을일은 없을것 같지만 우리는 배운 사람들이니까 다이나믹 프로그래밍을 통하여 쉽게 답을 구 할수 있다.

점화식은 dp[i][j]=dp[i-1][j]+dp[i][j-1] 이다.

#include <cstdio>
#include <algorithm>
using namespace std;
int dp[15][15], t, k, n;
int main() {
    for (int i = 1; i < 15; i++)
        dp[0][i] = i;
    for (int i = 1; i < 15; i++) {
        for (int j = 1; j < 15; j++) {
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
        }
    }
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &k, &n);
        printf("%d\n", dp[k][n]);
    }
    return 0;
}