파스칼의 삼각형

문제

15489번: 파스칼 삼각형

문제 설명

파스칼 삼각형은 아래와 같은 모양으로 이루어져 있다. 양 끝을 제외한 각 수는 자신의 바로 왼쪽 위의 수와 바로 오른쪽 위의 수의 합으로 되어있다.

이때 R번째 줄, C번째 수를 위 꼭짓점으로 하는 한 변이 포함하는 수의 개수가 W인 정삼각형과 그 내부를 생각하자. 정삼각형의 변과 그 내부에 있는 수들의 합을 구하고 싶다. 예를 들면, 3번 째 줄, 1번 째 수를 꼭짓점으로 하고 한 변이 포함하는 수의 개수가 4인 정삼각형과 그 내부에 있는 수의 합은 1+(1+3)+(1+4+6)+(1+5+10+10) = 42 이다.

주어진 R, C, W에 대해서 그에 해당하는 합을 구하는 프로그램을 작성하여라.

제한 사항

첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) 첫째 줄에 R번째 줄, C번째 수를 위 꼭짓점으로 하는 한 변이 포함하는 수의 개수가 W인 정삼각형과 그 내부에 있는 수들의 합을 출력한다.

입출력 예

입력	출력
3 1 4	42

아이디어

dp로 pascal[30][30] 만들어 놓고 출력만 하기

제출 코드

import java.io.IOException;
import java.util.Scanner;

public class Main {
    private int[][] pascal = new int[31][31];

    public void solution() throws IOException {
        pascal[1][1] = 1;
        pascal[2][1] = 1;
        pascal[2][2] = 1;
        pascal[3][1] = 1;

        for (int i = 1; i <= 30; i++) {
            pascal[i][1] = 1;
            pascal[i][i] = 1;
        }

        for (int i = 3; i < 30; i++) {
            for (int j = 2; j < 30; j++) {
                pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
            }
        }

        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int c = sc.nextInt();
        int w = sc.nextInt();

        int result = 0;
        for (int i = r; i < r + w; i++) {
            for (int j = 0; j <= i - r; j++) {
                result += pascal[i][c + j];
            }
        }
        System.out.println(result);

    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}