[백준 알고리즘] 백준 15489번 파스칼 삼각형 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 15489번 파스칼 삼각형 자바(Java)

1) 문제번호 : 15489번

 

2) 문제 출처

www.acmicpc.net/problem/15489

15489번: 파스칼 삼각형

 

2. 문제

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

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

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

 

3. 제약사항

- 

4. 입력

첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R)

 

5. 출력

첫째 줄에 R번째 줄, C번째 수를 위 꼭짓점으로 하는 한 변이 포함하는 수의 개수가 W인 정삼각형과 그 내부에 있는 수들의 합을 출력한다.

 

6. 풀이

- dp를 이용해서, i와 j가 같을 경우(nCr에서 n과 r이 같을 경우)와 j가 1일경우(nC0일경우)는 1로 둔다.

- 위의 조건이 아니라면 nCr의 값은 n-1Cr-1 + n-1Cr 이므로, 이 값을 더해준다.

 

7. 소스 코드

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int[][] dp = new int[31][31];
		
		int R = sc.nextInt();
		int C = sc.nextInt();
		int W = sc.nextInt();
		
		//1C1의 값은 1
		dp[1][1] = 1;
		
		//30줄
		for(int i=1;i<=30;i++) {
			for(int j=1;j<=i;j++) {
				//j가 i랑 같은 맨 뒤이거나, 맨 앞이 j가 1이라면 1로 설정
				//즉, 3C3도 1 3C0 일 경우 1이다
				if(j==i || j==1) dp[i][j] = 1;
				
				//아닐 경우에는 위의 왼쪽과 오른쪽의 합이 dp[i][j]가 된다.
				else 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+1;j++) {
				sum += dp[R+i][C+j];
			}
		}
		
		System.out.println(sum);		
	}
}

 

---