[C++] 백준 2775번 부녀회장이 될테야

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

풀이 1

DP의 top-down 방식으로 풀었다.
정답으로 채점되었지만, 더 효율적인 코드가 있을 것 같아서 다른 풀이를 생각해봤다.

코드 1

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> apartment(15, vector<int>(15));

int dp(int x, int y) {
    if(x == 0) return apartment[x][y] = y;
    
    if(apartment[x][y] > 0) return apartment[x][y];
    
    for(int i=1; i<=y; i++) {
        apartment[x][y] += dp(x-1, i);
    }
    return apartment[x][y];
}

int main()
{
    int T, cnt = 0;
    cin >> T;
    
    while(cnt < T) {
        cnt++;
        
        int k, n;
        cin >> k >> n;
        
        apartment.assign(15, vector<int>(15, 0));
        cout << dp(k, n) << "\n";
    }
    
    
    return 0;
}

풀이 2

DP의 bottom-up 방식으로 풀었다.
dp[k][n] = dp[k-1][n] + dp[k][n] 로 표현할 수 있다.

그리고 dp 배열의 값들을 미리 채워놓으면, 테스트케이스마다 dp[k][n]만 가져오면 된다.

코드 2

#include <iostream>

using namespace std;

int main()
{
    int dp[15][15] = {0};
    
    for(int j=1; j<15; j++) dp[0][j] = j;
    for(int i=1; i<15; i++) {
        dp[i][1] = 1;
        for(int j=1; j<15; j++) {
            dp[i][j] = dp[i][j-1] + dp[i-1][j];
        }
    }
    
    int T;
    cin >> T;
    
    while(T--) {
        int k, n;
        cin >> k >> n;
        cout << dp[k][n] << "\n";
    }
    
    return 0;
}