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

백준 온라인 저지(BOJ) 2775번 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

* 사용언어 : C언어, C++

 

1. 문제

한 아파트에 거주하려면 다음 조건을 만족해야 함

"a층의 b호에 살려면 (a-1)층 1호부터 b호까지 사람들의 수의 합만큼 데리고 살아야 함"

이때 k층 n호에는 몇 명이 살고 있는지 출력 (0층의 i호에는 i명이 살고 있음)

 

2. 풀이

문제가 상식적으로 말이 안돼서 처음에 해석할 때 좀 어려웠습니다.

난해한 문제 내용에 비해 규칙과 풀이는 간단했습니다.

 

0층의 1호는 1명, 2호는 2명, ... 14호에는 14명이 삽니다.

1층의 1호는 1명 (0층 1호)

1층의 2호는 3명 (0층 1호 + 0층 2호)

2층의 3호는 6명 (0층 1호 + 0층 2호 + 0층 3호)

...

입니다.

그리고 또 2층에서 같은 방식의 연산을 반복하면 됩니다.

 

층과 호수로 이루어진 아파트 모양의 2차원 배열을 선언하고,

위와 같은 연산을 1층부터 k 층까지 반복하면 답을 구할 수 있습니다.

 

불필요한 연산을 최소화하기 위해 14호가 아닌 n 호까지만 계산했고,

다음 Test Case 에서 재활용할 수 있게 값이 있으면 skip 하는 방식을 사용했습니다.

(동적할당법의 메모이제이션과 동일한 방식입니다)

 

3. 코드

#include <stdio.h>

int main() {
	int t;
	scanf("%d", &t);

	int arr[15][15] = { 0, };
	for (int i = 1; i < 15; ++i) {
		arr[0][i] = i;
	}

	int k, n;
	for (int i = 0; i < t; ++i) {
		scanf("%d %d", &k, &n);

		for (int y = 1; y <= k; ++y) {
			for (int x = 1; x <= n; ++x) {
				if (arr[y][x]) continue;

				for (int j = 1; j <= x; ++j) {
					arr[y][x] += arr[y - 1][j];
				}
			}
		}
		printf("%d\n", arr[k][n]);
	}
	
	return 0;
}