[백준] 16395번 : 파스칼의 삼각형 – JAVA [자바]

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

16395번: 파스칼의 삼각형

 

---

• 문제

 

 

---

• 문제 풀이

백준 16395번 파스칼의 삼각형은 실버 5 난이도의 수학, 그리고 DP 문제이다. 이 문제는 DP를 이용해서 파스칼의 삼각형을 만들기만 하면 된다. 그리고 정수 n과 k가 주어지는데 n번째 행의 k번째 수를 출력해주면 끝나는 문제이다.

 

우선 파스칼의 삼각형은 다음과 같이 생겼다. 이를 2차원 DP 테이블로 한번 만들어 볼 것이다. 우리는 n번째 줄까지 계산을 해야 하기 때문에 높이가 5인 DP 테이블이 필요하다. 그리고 k번째까지만 계산하면 되기 때문에 [n][k] 사이즈의 테이블을 만든다.

 

점화식은 다음과 같다. n번째 줄의 k번째 수는 dp [n][k] = dp [n-1][k-1] + dp [n-1][k]이다.

 

 

문제에서 주어진 첫 번째 예제를 예로 한번 보겠다. n = 5, k = 3이다. 물론 사이즈가 [5][5]인 테이블을 만들어서 파스칼의 삼각형을 다 만들 수도 있지만 우리가 필요한 거는 k번째 수이기 때문에 사이즈가 [5][3]인 테이블만 만들겠다. 따라서 사이즈가 [5][3]인 DP 테이블을 다음과 같이 만든다. 우선 첫 번째 줄의 첫 번째 수 [1][1]은 항상 1이다.

 

첫 번째 줄은 끝났기 때문에 두 번째 줄로 넘어간다. 전에 정의했던 점화식으로 풀도록 하겠다.

dp [2][1] = dp [1][0] + dp [1][1] = 0 + 1 = 1

dp [2][2] = dp [1][1] + dp [1][2] = 1 + 0 = 1

 

이제 세 번째 줄을 채워보도록 하겠다.

dp [3][1] = dp [2][0] + dp [2][1] = 0 + 1 = 1

dp [3][2] = dp [2][1] + dp [2][2] = 1 + 1 = 2

dp [3][3] = dp [2][2] + dp [2][3] = 1 + 0 = 1

 

이렇게 해서 네 번째 줄, 그리고 다섯 번째 줄도 마찬가지로 해준다.

dp [4][1] = dp [3][0] + dp [3][1] = 0 + 1 = 1

dp [4][2] = dp [3][1] + dp [3][2] = 1 + 2 = 3

dp [4][3] = dp [3][2] + dp [3][3] = 2 + 1 = 3

 

dp [5][1] = dp [4][0] + dp [4][1] = 0 + 1 = 1

dp [5][2] = dp [4][1] + dp [4][2] = 1 + 3 = 4

dp [5][3] = dp [4][2] + dp [4][3] = 3 + 3 = 6

 

이렇게 모든 계산을 다 하면 다음과 같은 DP 테이블이 나온다. 그리고 dp [n][k]만 출력해주면 된다.

 

---

• 코드

 

import java.io.*;
import java.util.*;
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[n+1][n+1];
        dp[1][1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }
        System.out.print(dp[n][k]);
    }
}

 

---

 

• 후기

이런 문제를 전에 한번 접해본 적이 있기 때문에 수월하게 풀 수 있었다.