백준 15489 파스칼 삼각형 문제풀이 (JAVA)

문제 링크

문제

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

이때 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인 정삼각형과 그 내부에 있는 수들의 합을 출력한다.

풀이

처음에 파스칼 삼각형을 만들었다.

for (int i = 1; i < 30; i++) {
     for (int j = 0; j < i + 1; j++) {
        if (j == 0 || j == i) {
            pascal[i][j] = 1;
            continue;
        }
        pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
     }
 }

삼각형의 맨 끝에는 1로 채우고, 맨 끝이 아니면, 자신보다 윗 행에서 자신의 열과 같은 열의 수 + 1칸 뒤의 수를 더해준다.
그 후에, 삼각형 변의 길이가 n이면 삼각형의 높이도 n인 점을 이용하여 삼각형의 꼭지점을 기준으로 범위 내 수들을 합한 값을 출력한다.

소스코드

import java.math.BigInteger;
import java.util.*;
import java.io.*;


public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int pascal[][] = new int[30][30];
        pascal[0][0] = 1;
        for (int i = 1; i < 30; i++) {
            for (int j = 0; j < i + 1; j++) {
                if (j == 0 || j == i) {
                    pascal[i][j] = 1;
                    continue;
                }
                pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
            }
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        final int TOP_POINT_COL = Integer.parseInt(st.nextToken());
        final int TOP_POINT_ROW = Integer.parseInt(st.nextToken());
        final int TRI_SIDE_COUNT = Integer.parseInt(st.nextToken());
        int triGrade = 1;
        int addTotal = 0;
        for (int i = TOP_POINT_COL; i < TOP_POINT_COL + TRI_SIDE_COUNT; i++) {
            for (int j = TOP_POINT_ROW; j < TOP_POINT_ROW + triGrade; j++) {
                addTotal += pascal[i-1][j-1];
            }
            triGrade++;
        }

        sb.append(addTotal);
        sb.append("\n");
        bw.write(sb.toString());

        bw.flush();
        br.close();
        bw.close();

    }


}