[백준/JAVA] 16395번: 파스칼의 삼각형

📖 문제

16395번: 파스칼의 삼각형

 

 

💡  풀이 방식

• DP

. 2차원 배열을조합 식 nCr = n-1Cr-1 + n-1Cr 을 활용해 채운다.

 - 첫 번째 열에 있는 칸과, 행=열인 칸은 1로 초기화

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

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int[][] dp = new int[31][31];
        for(int i = 1 ; i <= n ; i++) {
            dp[i][1] = 1;
            dp[i][i] = 1;
        }
        
        for(int i = 2 ; i <= n ; i++) {
            for(int j = 2 ; j < i ; j++) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }
        
        System.out.println(dp[n][k]);
    }
}
 

---

 

 

1회독	2회독	3회독	4회독	5회독
V