[BOJ] 2775번 부녀회장이 될테야 - JAVA

## Java 풀이 시 유의사항 ##
클래스명은 Main 으로 작성해야함!

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] arr = new int[15][15];

        // dp 테이블 초기화
        for (int i = 0; i < 15; i++) {
            for (int j = 1; j < 15; j++) {
                arr[i][1] = 1;  // i층 1호 = 1
                arr[0][j] = j;  // 0층 j 호 = j
            }
        }

        // dp 테이블 값 갱신
        for (int i = 1; i < 15; i++) {
            for (int j = 2; j < 15; j++) {
                arr[i][j] = arr[i-1][j] + arr[i][j-1];
            }
        }
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            int k = Integer.parseInt(br.readLine());
            int n = Integer.parseInt(br.readLine());
            sb.append(arr[k][n]).append("\n");
        }
        System.out.println(sb);
    }
}

📄 해설

• 전형적인 다이나믹 프로그래밍(Dynamic Programming, DP 문제라고 볼 수 있을 듯
• 모든 테스트 케이스에 사용되는 배열이 동일함
• 따라서 2차원 배열을 선언하고, 해당 배열에 먼저 0층의 거주민 수와 각 층의 1호 주민의 수를 먼저 초기화 함
• 0 층 j 호의 거주민 수 = i (1 <= j <= 14)
• i 층 1 호의 거주민 수 = 1 (1 <= i <= 14)
• 아래와 같은 점화식에 의하여 배열의 나머지 값들을 초기화 함
  • i 층 j 호의 거주민 수 = (i - 1) 층 j 호 거주민 수 + i 층 (j - 1) 호 거주민 수
• 이후 입력 값에 해당하는 배열 인덱스의 값이 결과가 됨