백준 2775번 문제(부녀회장이 될테야) C++로 풀기

2775번 부녀회장이 될테야

---

문제 요약

문제의 조건에 따른 집의 거주민 수를 출력한다.

---

코드

#include <iostream>

using namespace std;

int aprt[15][15]={0}; // 문제에서 아파트의 범위를 14x14로 제한했음
// 모든 호에 사는 사람을 구해놓고 입력 받음
int main()
{
  for(int j=0;j<15;j++) // 0층에 있는 사람 구함
  {
    aprt[0][j]=j+1;
  }
  for(int a=1;a<15;a++) // 1층부터 14층까지
  {
    for(int b=0;b<15;b++) // 0호부터 14호까지
    {
      for(int c=0;c<=b;c++) // 어느 호에 몇 명이 사는지 계산
      {
        aprt[a][b]+=aprt[a-1][c];
      }
    }
  }
  int t;
  cin>>t;
  for(int i=0;i<t;i++)
  {
    int k,n;
    cin >> k;
    cin >> n;  
    cout << aprt[k][n-1]<<"\n"; // 출력
  }
}

---

풀이

문제에 나와있는

• a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다
• 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다

이 두 규칙이 핵심이다.

케이스가 주어질 때마다 몇 층 몇 호에 몇 명이 사는지를 계산하는 것보다, 아파트 전체에서 몇 층 몇 호에 몇 명이 사는지를 다 구해놓고 케이스를 입력받아 출력하는 게 낫다고 생각했다.

for(int a=1;a<15;a++) // 1층부터 14층까지
{
   for(int b=0;b<15;b++) // 0호부터 14호까지
   {
      for(int c=0;c<=b;c++) // 어느 호에 몇 명이 사는지 계산
      {
         aprt[a][b]+=aprt[a-1][c];
      }
   }
}

3중 for문을 써 몇 층 몇 호에 몇 명이 사는지를 구했다.

---

주의점

출력시 "aprt[k][n]"가 아닌 "aprt[k][n-1]"를 출력해야 한다.