[백준] 2775번 : 부녀회장이 될테야 (JAVA)

1. 문제 분석

매우 쉬운 DP 문제이다. 피보나치 문제와 유사하다.

 

시간복잡도 : O(TxNxK) 

알고리즘 : DP

2. 문제 풀이

k층 n호의 인원수를 구하면된다. k-1층 n호까지의 인원의 합을 구하면된다.

• dp[k][n] = dp[k-1][1] + dp[k-1][2] + dp[k-1][3] .. + dp[k-1][n]
• dp[k][n-1] = dp[k-1][1] + dp[k-1][2] + dp[k-1][3] .. + dp[k-1][n-1]

아주 쉽다. 즉 같은 층 이전 호수 + 아래층 현재 호수를 더하면 된다.

• dp[k][n] = dp[k][n-1] + dp[k-1][n]

 

3. 코드 구현

import java.util.Scanner;

public class BOJ_2775 {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for(int i = 0; i < T; i++){
            int k = sc.nextInt();
            int n = sc.nextInt();
            int[][] dp = new int[k+1][n+1];

            for(int t = 0; t <= k; t++){
                for(int j = 1; j <= n; j++){
                    if(t == 0){
                        dp[t][j] = j;
                    }
                    else{
                        dp[t][j] = dp[t-1][j] + dp[t][j-1];
                    }
                }
            }
            System.out.println(dp[k][n]);
        }
    }


}