[BAEKJOON] NO.2775 부녀회장이 될테야

2040 단어 CbaekjoonC

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

처음에는 이전 층까지의 주민 수를 다 더하기 위해
재귀함수를 구현해야 한다고 생각했다.

그런데 재귀함수 구현이 잘 안되서,,ㅠ
다시 생각해보니까 2차원 배열이 떠올랐다.

  1. 2차원 배열에 주민 수를 먼저 저장한다
  2. 만든 2차원 배열을 바탕으로 k층 n호에 사는 거주민 수를 구한다.
    - (k-1)층의 1호부터 n호까지 살고 있는 거주민 수의 합

2차원 배열을 전부 다 만들기에는 층이 몇층이 될지 몰라서
입력받은 수만큼만 만들도록 했다.

동적할당을 써야하나 싶었는데,
반복문 안에서 만들었더니 그러지 않아도 됐다.

#include <iostream>
using namespace std;

// 부녀회장이 될테야
int main(void)
{
    int testcase = 0;
    cin>>testcase;

    int k_values[testcase];
    int n_values[testcase];
    for (int i = 0; i < testcase; i++)
    {
        cin>>k_values[i]>>n_values[i];
    }

    int sum = 0;
    
    for(int i=0; i<testcase; i++)
    {
        // 아파트에 숫자 채우기
        int apartment[k_values[i]][n_values[i]];
        for(int j=0; j<k_values[i]; j++)
        {
            for(int k=0; k<n_values[i]; k++)
            {
                if(j==0)
                {
                    apartment[j][k] = k+1;
                }
                else
                {
                    if(k==0)
                    {
                        apartment[j][k] = 1;
                    }
                    else
                    {
                        apartment[j][k] = apartment[j-1][k] + apartment[j][k-1];
                    }   
                }
            }
        }
        
	// k층 n호의 거주민 수 계산
        for(int z=0; z<n_values[i]; z++)
        {
            sum += apartment[k_values[i]-1][z];
        }

        cout<<sum<<endl;
        sum = 0;
    }
    return 0;
}

좋은 웹페이지 즐겨찾기