백준 2275 - 부녀회장이 될테야

www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

 

 

부녀회장이 될테야

 

#include <iostream>
#include <vector>

using namespace std;

struct house{
  int k;
  int n;
};

int main() {
  int num = 0;

  cin >> num ;

  vector<house> h(num);

  int home[15][15] = { 0 };

  for(int i = 0; i<num; i++){
    cin >> h[i].k >> h[i].n;
  }

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

  for(int i = 0; i<num; i++){
    cout << home[h[i].k][h[i].n] << endl;
  }
 
}

 

디피를 사용하면 보다 쉽게 풀수 있다. 디피를 사용하는 팁은 먼저 2차원 배열을 그리고 수가 채워지는 걸 하나 하나 그리다 보면 규칙이 발견되고, 규칙을 이용해서 푸는 것이다.