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

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

https://www.acmicpc.net/problem/2775

문제 접근

백준에서 에제로 준 입력과 출력을 하나씩 쓰다보면 규칙이 보이게 된다.
000 -> 0
001 -> 1
002 -> 2
003 -> 3
100 -> 0
101 -> 1
102 -> 3
103 -> 6
200 -> 0
201 -> 1
202 -> 4
203 -> 10
이때 103호에는 003호와 102호를 합친 값이 있고, 203호에는 103호와 202호를 합친 값이 있다.
이를 점화식으로 바꿔보면 (k0n)호 = k-10n호 + k0n-1호
코드로 바꿔보면 dp[floor][room] = dp[foor-1][n] + dp[floor][n-1]이 된다. 이를 코드로 바꾸면 다음과 같다.

Code

import java.io.*;

public class BOJ2775 {
    static int[][] dp = new int[15][15];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int T;
        T = Integer.parseInt(br.readLine());
        while (0 < T--){
            int k,n;
            k = Integer.parseInt(br.readLine());
            n = Integer.parseInt(br.readLine());
            sb.append(getPeopleCount(k, n) + "\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
    public static int getPeopleCount(int floor, int room){
        for (int i = 0; i <= floor; i++) {
            for (int j = 1; j <= room; j++) {
                if(dp[i][j] != 0){
                    continue;
                }
                if (i == 0)
                {
                    dp[i][j] = j;
                }
                else
                {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[floor][room];
    }
}