[백준] 15489번 : 파스칼 삼각형 – JAVA [자바]

https://www.acmicpc.net/problem/15489

15489번: 파스칼 삼각형

 

---

• 문제

 

 

---

• 문제 풀이

백준 15489번 파스칼 삼각형은 실버 5 난이도의 DP 문제이다. 이 문제에서는 정수 R, C, W가 주어진다. 그리고 R + W 만큼의 파스칼의 삼각형을 만들어야 한다. 왜냐하면 R번째 줄, C번째 수를 위 꼭짓점으로 하는 한 변이 포함하는 수의 개수가 W인 정삼각형 안에 있는 모든 수를 더한 값을 출력해야 하기 때문이다.

 

우선 2차원 DP 테이블을 만든다. DP [i][j]는 i번째 줄에서 j번째 수라고 하겠다. 그리고 다음과 같이 점화식을 정의하겠다.

dp [i][j] = dp [i-1][j-1] + dp [i-1][j]이다.

 

이제 문제에서 주어진 예제를 예시로 한번 풀어보겠다.

 

EX) R = 3, C = 1, W = 4

3번째 줄에서 1번째 수를 꼭짓점으로 삼고 한 변이 4인 다음과 같은 정삼각형에 포함되어 있는 모든 수를 구하면 된다.

 

우선 수가 1개만 있는 맨 위가 꼭짓점이므로 for-loop을 여기서 시작한다. 이 시작점은 dp [r][c]이다.

 

그리고 이 loop을 w번 반복한다. 한번 반복할 때마다 한 번씩 더 수를 더해주면 된다. 따라서 다음과 같이 for-loop을 쓸 수가 있다.

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

 

---

• 코드

 

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 <= r+w; 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];
            }
        }
        System.out.print(sum);
    }
}

 

---

• 후기

파스칼 삼각형의 DP 문제를 풀어본 적이 있어서 쉽게 풀 수 있었다.