백준 16395번 파스칼의 삼각형

Intro

이항계수를 삼각형 형태로 배열한 파스칼의 삼각형.
n번째 행의 k번째 수를 구하는 문제이다.
n=3, k=2라면 정답은 2이다.

Solution

1. 크기를 n으로 하여 삼각형을 의미하는 배열 arr을 미리 만들어둔다.
2. n번째 행의 k번째 수는 n-1번째 행의 k-1번째 수와 k번째 수를 더한 값이다.

Code

def main():
    n, k = map(int, input().split())
    arr = [[1]*i for i in range(1, n+1)]

    for i in range(2, n):
        for j in range(1, i):
            arr[i][j] = arr[i-1][j-1] + arr[i-1][j]

    print(arr[n-1][k-1])

main()