[백준 15489번] 파이썬 - 파스칼 삼각형

백준 15489 - 파스칼 삼각형

시간 제한 1초, 메모리 제한 512MB

# 조건

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

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

# 접근 방법

• 최대 크기인 30이므로 31 크기의 2차원 리스트를 생성해준다.
• 1, 1을 1로 초기화 한 후 주어진 조건에 따라 숫자를 채워나간다.
• 2번째 행부터 arr[i-1][j] + arr[i-1][j-1]로 값을 채워넣는다.
• 이후 각 행마다 더해야되는 수를 기록할 cnt 변수 선언, range(R, R+W)를 통해 행의 범위를 지정해주고 range(C, C+cnt)로 열의 범위를 지정해주며 2중 for문을 돌린다.
• 2중 for문이 끝날 때 마다 cnt += 1을 해주면 된다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from collections import defaultdict


R, C, W = map(int, input().split())
arr = [[0] * 31 for _ in range(31)]
arr[1][1] = 1
for i in range(2, 31):
    for j in range(1, 31):
        arr[i][j] = arr[i-1][j] + arr[i-1][j-1]
result = 0
cnt = 1

for i in range(R, R+W):
    for j in range(C, C+cnt):
        result += arr[i][j]
    cnt += 1
print(result)