백준 2775번 부녀회장이 될테야(C++)

문제 해결 방안 : 동적 계획법을 이용해서 해결했다.

문제 해결 소감 : 동적 계획법을 이용해서 처음 문제를 풀어봤다. 역시 끙끙 앓는 것보다 이미 나와있는 좋은 걸 빨리 흡수하는게 좋은 것 같다. 대충 찾아보니 새로운 다 구하지 말고 이미 구한 건 재활용해서 실행시간을 줄이는 게 동적 계획법의 특징인 것 같다. 자세한 건 공부해서 블로그에 한번 올려야 겠다.

#include <iostream>
#include <vector>
int T = 0;
int k = 0, n = 0; // 1<=k,n<=14
int arr[15][14] = {
    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
}; // a층 b호는 arr[a][b-1]임
int floor(int k, int n) // k행 n열이 실제로 궁금한 값
{
    if (arr[k][n] != 0)
    {
        return arr[k][n];
    }
    arr[k][n - 1] = floor(k, n - 1);
    arr[k - 1][n] = floor(k - 1, n);
    arr[k][n] = arr[k][n - 1] + arr[k - 1][n];
    return arr[k][n];
}

int main()
{
    std::cin >> T;
    for (int i = 0; i < T; ++i)
    {
        std::cin >> k >> n; // k층 n호
        std::cout << floor(k, n - 1) << '\n';
    }
    return 0;
}