[백준] 15489 파스칼 삼각형 - Dynamic Programming / Java

• 문제 링크

15489번: 파스칼 삼각형

 

• 풀이 과정

위 꼭짓점이 r, c 이고 변의 길이가 w 인 정삼각형을 포함하는 범위까지 파스칼 삼각형을 구한다.

이는 2차원 배열에서 계단 형태를 띄며 각 좌표의 값은 좌상단 값과 상단 값을 합한 값이 된다.

 

이 후 문제에 주어진 정삼각형의 범위의 모든 값을 합한 값을 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());

        int[][] dp = new int[r + w + 1][r + w + 1];

        dp[1][1] = 1;
        for (int i = 2; i < dp.length; i++) {
            for (int j = 1; j < i; j++)
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }

        int sum = 0;
        for (int i = 0; i <= w; i++) {
            for (int j = 0; j < i; j++)
                sum += dp[r + i][c + j];
        }

        bw.write(String.valueOf(sum));
        bw.flush();
    }

}