[Java/Python] 백준 15489번 - 파스칼 삼각형 (실버 4)

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 다이나믹 프로그래밍 (DP)

 

https://www.acmicpc.net/problem/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인 정삼각형과 그 내부에 있는 수들의 합을 출력한다.

---

 

DP로 배열을 채워 넣은 후 정해진 범위의 합만 구하면 되는 쉬운 문제였다.

 

Java 풀이

import java.io.*;
import java.util.StringTokenizer;


public class Main {	
	
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		try {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			int [][] data = new int[31][31];
			
			for(int i=1; i<31; i++) {
				for(int j=1; j<i+1; j++) {
					if(j == 1 || j == i) {
						data[i][j] = 1;
					} else {
						data[i][j] = data[i-1][j-1] + data[i-1][j];
					}
				}
			}
			
			int tmp = 1;
			int result = 0;
			for(int i=r; i<r+w; i++) {
				for(int j=c; j<c+tmp; j++) {
					result += data[i][j];
				}
				tmp++;
			}
			System.out.println(result);
			
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

 

Python 풀이

import sys
input = sys.stdin.readline

r, c, w = map(int, input().split())
data = [[0 for _ in range(31)] for _ in range(31)]

for i in range(1, 31):
    for j in range(1, i+1):
        if j == 1 or j == i:
            data[i][j] = 1
        else:
            data[i][j] = data[i-1][j-1]+data[i-1][j]

tmp = 1
result = 0
for i in range(r, r+w):
    for j in range(c, c+tmp):
        result += data[i][j]
    tmp += 1
print(result)