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

백준의 부녀회장이 될테야(2775) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

사람들을 데리고 살 수 있는 공식이 주어졌을 때, K층 N호에는 몇명이 살고 있는지 구해야 하는 문제이다.

지금부터 문제 해결을 위한 수식을 하나 정의해보자.

F[A][B] = C 라는 수식을 사용할 것인데, 이 수식의 의미는 다음과 같다.

F[A][B] = C : A층 B호에 살고 있는 사람의 수는 C명입니다.

즉 ! 0층의 X호에는 X명이 살고 있으므로, 위의 수식에 적용을 시켜보면...

F[0][1] = 1, F[0][2] = 2, F[0][3] = 3, ... , F[0][X] = X 가 될 것이다.

 

그렇다면 이 수식을 바탕으로 '1층'을 계산해보자.

F[1][1] 은 어떻게 될까 ? F[1][1]은 0층의 1호부터 1호까지의 사람의 수를 합친 것이므로 '1'이 될 것이다.

F[1][2] 는 어떻게 될까 ? F[1][2]는 0층의 1호부터 2호까지의 사람의 수를 합친 것이므로 1 + 2 = '3'이 될 것이다.

F[1][3] 은 어떻게 될까 ? F[1][3]은 0층의 1호부터 3호까지의 사람의 수를 합친 것이므로 1 + 2 + 3 = '6' 이 될 것이다.

F[1][4] 는 어떻게 될까 ? F[1][4]는 0층의 1호부터 4호까지의 사람의 수를 합친 것이므로 1 + 2 + 3 + 4 = '10'이 될 것이다.

 

그럼 '2층'을 계산해보자.

F[2][1] = 1층의 1호부터 1호까지의 사람의 수를 합친 것이므로 '1'이 될 것이다.

F[2][2] = 1층의 1호부터 2호까지의 사람의 수를 합친 것이므로 1 + 3 = '4'가 될 것이다.

F[2][3] = 1층의 1호부터 3호까지의 사람의 수를 합친 것이므로 1 + 3 + 6 = '10'이 될 것이다.

F[2][4] = 1층의 1호부터 4호까지의 사람의 수를 합친 것이므로 1 + 3 + 6 + 10 = '20'이 될 것이다.

 

그렇다면 위에서 이야기한 1층과 2층을 통해서 하나의 성질과 이를 통한 식을 도출해보자.

F[1][1] = 1.

F[1][2] = 1 + 2 = 3

F[1][3] = 1 + 2 + 3 = 6

F[1][4] = 1 + 2 + 3 + 4 = 10

위와 같이 수식을 적어보았는데, 빨강색으로 표시된 수색에 대해서 한번 살펴보자.

빨강색 수식을 과연 어디서 구할 수 있는지를 생각을 한번 해보자.

F[1][2]에 표시되어 있는 "1"은 F[1][1]의 값을 의미한다.

F[1][3]에 표시되어 있는 "1 + 2"는 F[1][2]의 값을 의미한다.

F[1][4]에 표시되어 있는 "1 + 2 + 3" 은 F[1][3]의 값을 의미한다.

즉 ! 우리는 여기서 F[1][X] 의 값은 F[1][X - 1] + @ 로 이루어져 있다는 것을 알 수 있다.

그렇다면 '@'는 어떤 값을 의미할까 ??

바로 자기 아래층 호수에 사는 사람의 수를 의미한다.

즉 ! F[1][3] = F[1][2] + F[0][3] , F[1][4] = F[1][3] + F[0][4] 로 이루어져 있다는 것이다.

 

위에서 계산한 '2층'에서도 똑같이 적용된다는 것을 알 수 있다.

따라서 우리는 여기서 하나의 점화식을 알아낼 수 있다.

F[K][N] = F[K][N - 1] + F[K - 1][N] 이라는 것이다.

이를 통해 문제를 해결할 수 있다.

 

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 15
using namespace std;
 
int N, K;
int Arr[MAX][MAX];
 
void Initialize()
{
 
}
 
void Input()
{
    cin >> K >> N;
}
 
void Solution()
{
    for (int i = 1; i <= N; i++) Arr[0][i] = i;
    for (int i = 1; i <= K; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            Arr[i][j] = Arr[i - 1][j] + Arr[i][j - 1];
        }
    }
    cout << Arr[K][N] << endl;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}