[ 백준 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] 이라는 것이다.
이를 통해 문제를 해결할 수 있다.
[ 소스코드 ]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#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;
}
|
cs |