본문 바로가기

알고리즘 관련/BOJ

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] 이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)10277 JuQueen  (0) 2017.01.15
BOJ)2877 4와 7  (0) 2017.01.15
BOJ)5480 전함  (0) 2017.01.14
BOJ)10167 금광  (0) 2017.01.14
BOJ)9184 신나는 함수 실행  (0) 2017.01.14