[자바] 백준 16395 - 파스칼의 삼각형 (java)

 문제 : boj16395

---

 

필요 알고리즘 개념

• 다이나믹 프로그래밍 (DP, 동적계획법)
  
  • 파스칼의 삼각형을 한쪽으로 전부 밀어보면 규칙이 보인다. DP로 미리 값을 구한 후, n과 k에 따라 해당하는 값을 출력해주면 된다. DP 문제긴한데 DP라기보다는 그냥 규칙찾는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  문제에서 제시된 파스칼 삼각형을 코드로 어떻게 표현할지 생각해보자. 파스칼 삼각형을 좌측으로 쭉 밀어서 2차원 배열로 생각해보자.  아래 이미지는 파스칼 삼각형에서 4번째줄까지 좌측으로 밀어서 배열로 표현해본 것이다.

 

  위에서 얘기한대로 진행해도 상관없지만, 하삼각행렬(Lower Triangular Matrix) 형태이므로 가변배열로 표현하면 좀 더 효율적이다. 자바에선 int[][] arr = new int[n][]; 이후 arr[0] = new int[1]; arr[1] = new int[2]; ... 이런식으로 가변배열을 만들 수 있다.

 

  이제 자료구조(가변배열을 통한 하삼각행렬 형태)는 정했으니, n의 최대값인 30까지 미리 파스칼의 삼각형을 만들어보자. 위에서부터 아래로 내려가면서 자기자신의 값을 아래칸에 더해주면 된다.

 

  이후 입력받은 n, k에 대해 배열의 n행 k열 값을 출력해주면 답이다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final int LIMIT = 30;
    private int[][] getPascalTriangle() {
        int[][] arr = new int[LIMIT+1][];
        for (int i = 1; i <= LIMIT; i++) {
            arr[i] = new int[i+1];
        }
        arr[1][1] = 1;
        for (int i = 1; i < LIMIT; i++) {
            for (int j = 1; j <= i; j++) {
                arr[i+1][j] += arr[i][j];
                arr[i+1][j+1] += arr[i][j];
            }
        }
        return arr;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] arr = getPascalTriangle();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        System.out.println(arr[n][k]);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}