[C++] BOJ (백준) 2775 : 부녀회장이 될테야

문제

2775번: 부녀회장이 될테야 (acmicpc.net)

2775번: 부녀회장이 될테야

코드

#include <iostream>

using namespace std;

int dp[15][15];

int getResidents(int floor, int room) {
  if (dp[floor][room] != 0) return dp[floor][room];
  for (int i = 1; i <= room; i++) {
    dp[floor][room] += getResidents(floor - 1, i);
  }
  return dp[floor][room];
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  for (int i = 1; i <= 14; i++) {
    dp[0][i] = i;
  }

  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    int k, n;
    cin >> k >> n;
    cout << getResidents(k, n) << '\n';
  }
  return 0;
}

 

설명

각 호에 사는 사람의 수를 dp 배열에 저장한다.
dp 배열에 저장된 값이 있다면 바로 반환하고,
그렇지 않다면 문제에서 주어진 점화식으로 dp 배열에 값을 저장한 후 반환한다.

DP를 사용하지 않아도 통과는 되지만 시간 차이가 굉장히 많이 났다.