백준 16395 파스칼의 삼각형 JAVA 풀이 (DP, 조합)

🔗 문제 링크

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

 

📌 문제 개요

파스칼의 삼각형에서 N번째 줄의 K번째 값을 구하는 문제이다.
각 값은 바로 위의 두 값의 합으로 구성되는 특징을 가진다.

 

📌 접근 방법

이 문제는 DP 방식으로 직접 삼각형을 구성하거나
조합 공식으로도 해결할 수 있다.

 

직관적인 이해를 위해 2차원 배열을 이용한 DP 방식으로 풀이

 

📌 핵심 아이디어

• 양 끝 값은 항상 1
• 내부 값은 위 두 값의 합

점화식

arr[i][j] = arr[i-1][j-1] + arr[i-1][j]

 

또한 이 문제는 (N-1)C(K-1)과 동일하다

 

📌 전체 코드

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

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[][] arr = new int[31][31];

        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= i; j++){
                if(j == 1 || j == i){
                    arr[i][j] = 1;
                } else {
                    arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
                }
            }
        }

        System.out.println(arr[N][K]);
    }
}

---

📌 정리

• 파스칼 삼각형 기본 문제
• DP로 구현하면 직관적으로 해결 가능
• 조합으로도 풀이 가능 (수학적 접근)

한 줄 요약 : 파스칼 삼각형은 “위 두 값의 합” 규칙이다.