2775번 : 부녀회장이 될테야

문제는 다음과 같습니다.

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

2775번: 부녀회장이 될테야

 

풀이 코드는 다음과 같습니다.

#include <iostream>

using namespace std;

int main(void) {
	int arr[15][15]={{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}};
  for(int i{1};i<15;i++)
    {
      for(int j{1};j<15;j++)
        {
          if(j==1)
          {
            arr[i][j]=1;
          }
          else
          {
            arr[i][j]=arr[i-1][j]+arr[i][j-1];
          }

        }
  
    }
  int n;
  cin>>n;
  for(int i{0};i<n;i++)
    {
      int a,b;
      cin>>a>>b;
      cout<<arr[a][b]<<endl;
    }
return 0;
}

이 문제의 포인트는 a동 b호에 살면, 그 아래 층에 있는 a-1동의 1호부터 b호까지의 인원의 합이 되어야 한다는 점입니다.

하지만 1호는 1명만 살아도 조건을 만족하므로 a동과 무관하게 1이며, 알고싶은 a동 b호의 인원의 경우, 옆 호수인 a동 b-1호가 이미 a-1동에서 1호부터 b-1호까지의 인원의 합을 가지고 있으므로 a동 b-1호의 인원에 추가로 a-1호의 b동 인원만 더해주면 구할 수 있습니다. 이를 수식으로 나타내면

a[x][y] = a[x][y-1] + a[x-1][y] (x>0 , y>1) 입니다.

y=1인 경우만 예외처리를 해주고 나머지는 모두 구한 다음, 두 수를 입력받아 필요한 인원을 도출하면 되는 문제입니다.