[백준] 부녀회장이될테야 - 2775번

부녀회장이 될테야 

0.5 초 (추가 시간 없음)

128 MB

104395

59014

50087

57.510%

 

문제

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

이 아파트에 거주를 하려면 조건이 있는데, “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

예제 입력 1 복사

2
1
3
2
3

예제 출력 1 복사

6
10

 

알고리즘 분류

• 수학
• 구현
• 다이나믹 프로그래밍

 

코드

// 메모리:     17540KB
// 속도 : 228 MS
package 부녀회장이될테야;

import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;

/*
    [시간복잡도] -> O(N^2)
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new StringReader(input()));

        // 테스트 케이스의 수 입력
        int numberOfTestCases = Integer.parseInt(br.readLine());

        // 각 테스트 케이스 처리
        for (int t = 0; t < numberOfTestCases; t++) {
            int floor = Integer.parseInt(br.readLine());
            int room = Integer.parseInt(br.readLine());
            System.out.println(calculateResidents(floor, room));
        }

        br.close();
    }

    // 특정 층의 특정 호에 거주하는 주민 수를 계산하는 메서드
    public static int calculateResidents(int floor, int room) {
        // 아파트를 표현하는 2차원 배열
        int[][] apartment = new int[floor + 1][room + 1];

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

/*
        동적 계획법을 적용하여 각 층과 각 호의 거주민 수 계산
        첫 번째 루프는 1층부터 입력으로 주어진 floor 층까지 각 층을 반복합니다. currentFloor 변수는 현재 계산 중인 층을 나타냅니다.               */
        for (int currentFloor = 1; currentFloor <= floor; currentFloor++) {
/*
            두 번째 루프는 1호부터 입력으로 주어진 room 호까지 각 호를 반복합니다.
            currentRoom 변수는 현재 계산 중인 호를 나타냅니다. 이 루프 내에서 currentFloor 층의 각 호에 거주하는 사람 수를 계산          */
            for (int currentRoom = 1; currentRoom <= room; currentRoom++) {
/*
            세 번째 루프는 현재 호 (currentRoom)의 거주민 수를 계산하기 위해, 바로 아래층 (currentFloor - 1)의 1호부터 currentRoom호까지의 거주민 수를 합산합니다.
            i 변수는 현재 합산 중인 아래층의 호수를 나타냅니다.
            apartment[currentFloor][currentRoom] += apartment[currentFloor - 1][i]는 currentFloor 층의 currentRoom 호에 거주하는 사람 수를 아래층의 1호부터 currentRoom 호까지의 거주민 수의 합으로 설정합니다.
*/
                for (int i = 1; i <= currentRoom; i++) {
                    apartment[currentFloor][currentRoom] = apartment[currentFloor][currentRoom] + apartment[currentFloor - 1][i];
                }
            }
        }

        // 주어진 층과 호수의 거주민 수 반환
        return apartment[floor][room];
    }

    /*
    [예제 출력]
        6
        10
     */
    static String input(){
//        return "2\n"+
//                "1\n"+
//                "3\n"+
//                "2\n"+
//                "3";
        return "1\n"+
                "14\n"+
                "14\n";
    }
    /*
        [층별 호수 거주인원 상태 값]
        * 참고로 0호는 존재하지 않지만 배열 0번째 인덱스에 0을 추가한 것은 편의상 넣어두었음.

                            1호 2호 3호  4호  5호 ... room
        0층(floor):      {0, 1, 2,  3,  4,   5   ...   }
        1층:             {0, 1, 3,  6,  10,  15   ...  }
        2층:             {0, 1, 4,  10, 20, 35   ...  }
        3층:             {0, 1, 5,  15, 35, 70   ...  }
        4층:             {0, 1, 6,  21, 56, 126   ...  }
        5층:             {0, 1, 7,  27, 83, 209   ...  }


        [1층부터 k층까지 계산]

        하나. currentFloor = 1일 때:
            - currentRoom = 1일 때:
                - apartment[1][1] = apartment[0][1] = 1(1층 1호에는 0층 1호의 사람 수가 삽니다.)

            - currentRoom = 2일 때:
                - apartment[1][2] = apartment[0][1] + apartment[0][2] = 1 + 2 = 3 (1층 2호에는 0층 1호와 2호의 사람 수의 합이 삽니다.)

            - currentRoom = 3일 때:
                - apartment[1][3] = apartment[0][1] + apartment[0][2] + apartment[0][3] = 1 + 2 + 3 = 6 (1층 3호에는 0층 1호, 2호, 3호의 사람 수의 합이 삽니다.)

        둘. currentFloor = 2일 때:
            - currentRoom = 1일 때:
                - apartment[2][1] = apartment[1][1] = 1 (2층 1호에는 1층 1호의 사람 수가 삽니다.)

            - currentRoom = 2일 때:
                - apartment[2][2] = apartment[1][1] + apartment[1][2] = 1 + 3 = 4 (2층 2호에는 1층 1호와 2호의 사람 수의 합이 삽니다.)

            - currentRoom = 3일 때:
                - apartment[2][3] = apartment[1][1] + apartment[1][2] + apartment[1][3] = 1 + 3 + 6 = 10 (2층 3호에는 1층 1호, 2호, 3호의 사람 수의 합이 삽니다.)

     */
}