[C++] 백준 2775번: 부녀회장이 될테야

2775번: 부녀회장이 될테야

이 문제는 종이에 직접 적어가며 풀면 금방 푼다.

주어진 조건대로 수를 채워나가면 아래와 같은 표를 얻을 수 있다.

피보나치수열과 비슷한 느낌으로 수를 더해나간다.

맨 아래 0층은 1부터 쭉 수를 더해나가고, 각 층의 1호는 1로만 채워나간다.

연산은 1층의 2호부터 오른쪽으로 쭉 나아가며 한 층씩 올라가는데,

문제에서 주어진 것처럼 아래층의 해당 호수까지 숫자를 다 더해나가는 방법도 있지만,

바로 왼쪽과 아래칸의 합으로도 같은 결과를 얻을 수 있다.

바로 왼쪽 칸이 아래칸을 제외한 합이기 때문이다.

이를 활용하여, K와 N이 입력되면 (K + 1) * N의 크기를 갖는 배열을 선언하고 위의 규칙대로 끝까지 채워나간 뒤 마지막 칸의 값을 출력하면 된다. 이때 K + 1인 이유는 0층부터 시작하기 때문이다.

답을 검토할 떄는 위에서 구한 표와 비교해보면 된다. 엑셀에서 작업해서 정확하다.

 

#include <cstdio>

using namespace std;

int main()
{
	int T, K, N;
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d", &K, &N);
		int* apt = new int[(K + 1) * N];
		for (int i = 0; i < N; i++) {
			apt[i] = i + 1;
		}
		for (int j = 0; j < K + 1; j++) {
			apt[j * N] = 1;
		}
		for (int j = 1; j < K + 1; j++) {
			for (int i = 1; i < N; i++) {
				apt[j * N + i] = apt[(j - 1) * N + i] + apt[j * N + (i - 1)];
			}
		}
		printf("%d\n", apt[(K + 1) * N - 1]);
		delete[] apt;
	}
	return 0;
}