[2775] 부녀회장이 될테야

✔ 부녀회장이 될테야

[백준 2775]

문제 분석하기

조합의 점화식을 도출하는 방법을 응용해 이 문제에 사용할 점화식을 도출

손으로 풀어보기

1. N이 14이므로 이에 따라 DP 배열을 선언
   • D[N + 1][N + 1] = D[15][15]
2. DP 배열의 값을 초기화
   • 1호실에는 항상 값을 1로 초기화해야 하므로 D[i][1] = 1
   • 0층 i호의 수는 i로 초기화해야 하므로 D[0][i] = i
3. 점화식으로 DP 배열의 값을 채움
   • a층의 b호에 살려면 자신의 아래층인 a - 1층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데리고 살아야 하므로
     D[a][b] = D[a - 1][0] + D[a - 1][1] + ... + D[a - 1][b - 1] + D[a - 1][b] 
     이때 a층 b호는 a층 b - 1호의 값에서 자기 아래층인 a - 1층 b호의 사람 수만 더하여 일반화된 점화식을 도출
   • D[i][j] = D[i][j - 1] + D[i - 1][j]
4.  D[K][N]의 값을 출력함

슈도코드 작성하기

T(테스트 케이스) K(층수) N(호수)
D(DP 배열)
for(i -> 14만큼 반복하기) {
    D 배열 초기화하기
    D[i][1] = 1
    D[0][i] = i
}
for(i -> 1 ~ 14) {
    for(j -> 2 ~ 14) {
        D[i][j] = D[i][j - 1] + D[i - 1][j]
    }
}
for(T 개수) {
    K와 N값을 입력받음
    D[K][N] 출력하기
}

코드 구현하기

/**
 * 2775) 부녀회장이_될테야
 */
public class D078_2775 {
    static int T, K, N;
    static int[][] D;

    public static void main(String[] args) {
        // D(DP 배열)
        D = new int[15][15];
        // D 배열 초기화하기
        for (int i = 0; i < 15; i++) {
            D[i][1] = 1;
            D[0][i] = i;
        }
        // 점화식으로 D 배열 값 채우기
        for (int i = 1; i < 15; i++) {
            for (int j = 2; j < 15; j++) {
                D[i][j] = D[i][j - 1] + D[i - 1][j];
            }
        }
        Scanner sc = new Scanner(System.in);
        // T(테스트 케이스)
        T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            // K(층수)
            K = sc.nextInt();
            // N(호수)
            N = sc.nextInt();
            System.out.println(D[K][N]);
        }
    }
}