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

 

a 층의 b 호에 살려면 자신의 아래 (a-1) 층의 1호부터 b 호까지 사람들의 수의 합만큼 사람들을 데려와 살아햐 하는

조건과 k 와 n 을 입력받으면 k 층에 n 호의 거주자 수를 출력하는 문제입니다.

아파트 층수는 0층부터 시작하고 호수는 1호부터 시작하며, 0층의 i 호에는 i 명이 살고있고

k 와 n 은 1에서 14까지의 숫자를 입력받을 수 있습니다.  

 

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

public class p2775 {
    static int T, k=0, h=0;
    static int apart[][] = new int[15][15];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();

        //0층에는 호수 숫자만큼 거주자
        for (int i=1; i<15; i++) {
            apart[0][i] = i;
        }

        countingResidents();

        T = Integer.parseInt(br.readLine());

        for(int j=0; j<T; j++){

            k = Integer.parseInt(br.readLine());
            h = Integer.parseInt(br.readLine());

            sb.append(apart[k][h]).append("\n");
        }

        System.out.println(sb);
    }

    public static void countingResidents() {

        for(int i=1; i<15; i++) {

            for(int j=1; j<15; j++) {

                for(int k=1; k<=j; k++) {

                    apart[i][j] += apart[i-1][k];
                }
            }
        }
    }
}

 

동적계획법인 DP(Dynamic Programing) 를 이용해서 풀었습니다.

0층에서  i 호에는 i 명이 살고있으니 먼저 0층 거주자 수를 초기화하고 0층의 거주자수를 이용해

1층부터 14층까지 거주자수를 구해서 2차원 배열에 저장합니다. 그리고 k 와 n 을 입력받으면 

k 층 n 호 위치에 해당하는 2차원 배열 값을 StringBuffer 에 담아 한꺼번에 출력했습니다.