BOJ 2775 부녀회장이 될테야

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층에 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있나를 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층에 i호에는 i명이 산다.

---

규칙찾으려고 이것저것 해봤지만 결국 포기했다.

그냥 하나하나 채워나가야 하는 것 같다.

그려보면 알겠지만 맨 아랫층은 123456, 맨 왼쪽줄은 1명씩 산다.

k층의 n호에는 (k-1층 n호) + (k층 n-1호) 명이 산다는 규칙을 발견할 수 있다.

따라서 소스는 아래와 같다.

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

// 2775 부녀회장이 될테야 #include<stdio.h> #define FOR(i,j) for(int i=0;i<j;i++) int main() { int T, k, n; int apt[15][15] = { 0, }; // 1더해서 구할 것이므로 15칸씩 선언 scanf("%d", &T); while (T--) { scanf("%d", &k); scanf("%d", &n); k++; // 0층부터지만 호와 맞추기 위해서 편의상 +1 FOR(i, n) // 0층의 i호에 i명씩 초기값 넣어준다. (i=0부터이므로 +1) apt[0][i] = i+1; FOR(i, k) // 1호에 초기값 1 apt[i][0] = 1; for (int i = 1;i < k;i++) { for (int j = 1;j < n;j++) { apt[i][j] = apt[i - 1][j] + apt[i][j - 1]; // 왼쪽값, 아래쪽값 더해서 현재 값 구함 } } printf("%d\n", apt[k-1][n-1]); // 배열은 0부터이므로 -1씩 해줘야한다. 층은 0층부터지만 위에서 +1해줬다. FOR(i, 14) { FOR(j, 14) { printf("%3d", apt[i][j]); } printf("\n"); } } }