[BOJ_15489] 파스칼의 삼각형

설명

---

기본 DP문제로 워밍업 용으로 좋은 문제 인 것 같습니다. 문제에서 주어진 파스칼의 삼각형 공식을 사용했으며 (오른쪽 위 왼쪽 위를 더하면 아래의 조합 경우의 수가 나옴) 이때, 문제에서 주어진 삼각형의 경우의 수만큼 더했습니다.

 

코드

---

package BOJ.Dynamic_Programming;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_15489 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] str = in.readLine().split(" ");

        int R = Integer.parseInt(str[0]) - 1;
        int C = Integer.parseInt(str[1]) - 1;
        int W = Integer.parseInt(str[2]);

        int[][] dp = new int[31][31];

        for (int i = 0; i < 31; i++){
            for (int j = 0; j <= i; j++){
                if(j == 0 || i == j){
                    dp[i][j] = 1;
                }
                if(dp[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }
            }
        }

        int ans = 0;

        for (int i = R; i < R + W; i++){
            for (int j = C; j <= C + (i - R); j++){
                ans += dp[i][j];
            }
        }
        System.out.println(ans);
    }
}

 

15489번: 파스칼 삼각형