<코테 챌린지> 부녀회장이 될테야 (백준 2775번)

❓ 문제

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

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

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

📥 입력

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

📤 출력

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

⛔ 제한

• 1 ≤ k, n ≤ 14

📥 예제 입력

2
1
3
2
3

📤 예제 출력

6
10

 

👩🏻‍💻 내 코드

package baekjoon.코테챌린지;

import java.util.Scanner;

public class 부녀회장이될테야 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int T = in.nextInt();

        for (int t = 0; t < T; t++) {
            int k = in.nextInt(); // 층
            int n = in.nextInt(); // 호

            int[][] apt = new int[k + 1][n + 1];

            // 0층 초기화 (0층의 i호에는 i명이 산다)
            for (int i = 1; i <= n; i++) {
                apt[0][i] = i;
            }

            // 각 층과 호의 사람 수 계산
            for (int i = 1; i <= k; i++) { // 1층부터 k층까지
                for (int j = 1; j <= n; j++) { // 1호부터 n호까지
                    apt[i][j] = apt[i][j - 1] + apt[i - 1][j];
                }
            }

            System.out.println(apt[k][n]);
        }

    }
}

 

💡 코드 접근

 

재귀적 관계를 가진 아파트 구조를 계산하는 문제

• 0층의 i호에는 i명이 산다.
• k층의 n호에 사는 사람 수는, 아래층 (k-1)층의 1호부터 n호까지 사람 수의 합이다.

>> 위 조건들로 2차원 배열을 이용해 각 층과 호에 있는 사람 수를 계산할 수 있다

 

1. 먼저, 2차원 배열을 만들어 각 층과 호의 거주민 수를 저장한다.

• 층은 0층부터 k층까지 존재하므로, 배열에서 인덱스를 맞추려면 층의 개수가 k + 1이 되어야 한다.
• 각 층의 호는 1호부터 n호까지 존재합니다. 따라서 배열의 인덱스에서 n호까지 접근하려면 n + 1 크기의 배열이 필요하다.

int[][] apt = new int[k + 1][n + 1];

 

 

 

2. 0층은 각 호의 번호가 사람 수이므로 0층의 i호에는 i명이 산다고 미리 설정한다.

// 0층 초기화 (0층의 i호에는 i명이 산다)
for (int i = 1; i <= n; i++) {
    apt[0][i] = i;
}

 

 

3. 1층부터 k층까지 각 호의 사람 수는 그 아래층 1호부터 n호까지의 합

// 각 층과 호의 사람 수 계산
for (int i = 1; i <= k; i++) { // 1층부터 k층까지
    for (int j = 1; j <= n; j++) { // 1호부터 n호까지
        apt[i][j] = apt[i][j - 1] + apt[i - 1][j];
    }
}

 

 

4. 테스트 케이스마다 k층의 n호에 사는 사람 수를 출력

System.out.println(apt[k][n]);