[백준 2775] 부녀회장이 될테야 (DP)

 

 

 

 

 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(bf.readLine());
        
        for(int tc = 0; tc < t; tc++) {
            
            int k = Integer.parseInt(bf.readLine()); 
            int n = Integer.parseInt(bf.readLine());
            
            int[][] dp = new int[k + 1][n + 1]; 
            
            for(int i=1; i<=n; i++) {
                dp[0][i] = i;
            }
            
            for(int i=1; i<=k; i++) {
                int sum = 0;
                for(int j=1; j<=n; j++) {
                    sum += dp[i - 1][j];
                    dp[i][j] = sum;
                }
            }
            
            System.out.println(dp[k][n]);
        
        }
        
    }
}

 

Scanner, BufferedReader 속도 차이

 

 

DP 연습

작은 문제로 쪼개서 -> 맨 아래부터 풀어나가기

 

 

이렇게도 있음

k층 n호의 사람 수 = 같은 층의 이전 호 + 아래 층의 같은 호 

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