_2775

문제출처: https://www.acmicpc.net/problem/2775

 

2775번: 부녀회장이 될테야

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 <= k <= 14, 1 <= n <= 14)

www.acmicpc.net

계차수열에 관한 문제다. 실제로 표로 그려 규칙을 찾아보면 같은층의 왼쪽(K, N-1)과 바로 아래층(K-1, N)의 수를 합친 것과 같음을 알 수 있다. 따라서 int형 2차원 배열 arr에 각 층의 인원 수를 적은 후 arr[K][N]을 리턴해주면 된다.

 

#include <iostream>

using namespace std;

int arr[15][15];

int residentNumber(int K, int N) { // K층, N호

	for (int i = 1; i <= N; i++) {
		arr[0][i] = i;
	} // 0층의 주민 수 1, 2, 3 ...은 계차수열 법칙을 따르지 않으므로 따로 정의해준다.

	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];
		}
	} // 같은 층의 왼쪽 (arr[i-1][j]) + 바로 아래층 (arr[i][j-1])의 합이
      // arr[i][j], 즉 K'층 N'호의 인원 수.

	return arr[K][N];
}

int main() {
	int T, K, N;

	cin >> T; // Test case 수를 입력 받는다.
	
	for (int i = 0; i < T; i++) {
		cin >> K;
		cin >> N;
		cout << residentNumber(K, N) <<endl;
	}
}

 

 

 

 

 

 

 

'백준 풀이' 카테고리의 다른 글

while_10951  (0) 2020.08.14
_1002  (0) 2020.08.12
_10871  (0) 2020.08.11
Brute Force_1436  (0) 2020.08.11
recursive_11729  (0) 2020.08.09

댓글