백준 15489 파스칼 삼각형

17.18m

나의 답

import sys
input = sys.stdin.readline

r, c, w = list(map(int, input().rstrip().split()))
tri = [[] for _ in range(31)]
tri[1].append(1)
tri[2].append(1)
tri[2].append(1)

for i in range(3, 31):
    for j in range(i):
        if (j == 0) or (j == i - 1):
            tri[i].append(1)
            continue
        tri[i].append(tri[i - 1][j - 1] + tri[i - 1][j])

res = 0
for i in range(w + 1):
    for j in range(i):
        res += tri[r + i - 1][c + j - 1]

print(res)

행과 열의 깊이가 깊지 않아서 간단한 구현이라 생각하고 풀었다.
그런데 알고리즘 유형을 보니 DP..라길래 답을 조금 개선해봤다..!

개선된 답

import sys
input = sys.stdin.readline

r, c, w = list(map(int, input().rstrip().split()))
tri = [[1] * i for i in range(31)]

for i in range(3, 31):
    for j in range(1, i - 1):
        tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j]

res = 0
for i in range(w + 1):
    for j in range(i):
        res += tri[r + i - 1][c + j - 1]

print(res)

성능은 정말 조금, 코드라인은 많이 줄었다!