[백준] 15489 파스칼 삼각형 JAVA

혅·2024년 3월 20일

1일1백준 -Java-

목록 보기

54/60

문제

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

이때 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

예제 출력

내가 했던 풀이 방법

파스칼 삼각형을 저장할 2차원 배열 pascal을 선언한다. (size는 R+W이다.) 배열의 일부는 사용하지 않을 것이다.
첫 번째 line과 두 번째 line을 1로 넣어준다.
1부터 R+W-1(필요로하는 마지막 라인)까지 for문을 돌린다. (i)
1부터 i(3번 for문)까지 for문을 돌린다. (j)
j가 1또는 i(라인의 마지막 수)일 때는 1을 pascal에 저장해준다. 그렇지 않을 경우 이전 라인에 두 수를 더한 값을 pascal에 저장해준다.
(두 수는 j-1과 j이다. 예를 들어 3번째 라인에서 2번째 요소는 2번째 라인에서 1,2번째 요소를 더해준 값) -> 5번은 i가 3이상일 경우에만 실행해준다. (1,2번째 line은 1번에서 저장해두었기 때문에 1,2번 line은 sum을 계산하기 위해 필요하다.)
i(현재 line)이 R보다 크거나 같고, j가 C보다 크면서 C+line보다는 작을 경우 현재 pascal의 값을 sum에 더해준다. (line은 현재 line에서 어디까지를 더해주어야 하는지를 나타낸다. 즉, 현재 3번째 줄이고, line이 1일 경우 3부터 3+1(4)까지 더해준다는 의미이다.)
i가 R보다 크거나 같고, 현재 line의 마지막 수일 때 line을 증가시켜준다.
모든 for문이 끝난 후 sum을 출력한다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

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

        int[][] pascal = new int[R+W][R+W];
        pascal[1][1] = 1;
        pascal[2][1] = 1;
        pascal[2][2] = 1;
        int sum = 0;
        int line = 0;
        for(int i=1; i<=R+W-1; i++) {
            for(int j=1; j<=i; j++) {
                if(i>=3) {
                    if(j==1 && j==i) {
                        pascal[i][j] = 1;
                    } else {
                        pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
                    }
                }
                
                if(i>=R) {
                    if(j>=C && j<=C+line) {
                        sum += pascal[i][j];
                    }
                }
            }
            if(i>=R) {
                line++;
            }
        }

        System.out.print(sum);
        
    }
}