백준 16395 파스칼의 삼각형(JAVA)

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

16395번: 파스칼의 삼각형

 

파스칼의 삼각형을 배열로 표현하면

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

.... 이런 식으로 진행됩니다.

따라서 i - 1, j - 1 인덱스에 있는 value와 i - 1, j 인덱스에 있는 값을 더해서 i, j에다 저장하면 파스칼의 삼각형이 만들어집니다.

 

import java.util.*;
 
public class Main {
    static int dp[][] = new int[31][31];
 
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        sc.close();
 
        int ans = paskal(N, K);
 
        System.out.println(ans);
    }
 
    private static int paskal(int n, int k) {
        dp[1][1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if (j == 1 || j == i) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }
            }
        }
 
        return dp[n][k];
    }
}