BOJ/백준-16395-python

문제

풀이

• 점화식으로 푸는 문제이므로 dp 알고리즘을 활용하면 쉽게 구현할 수 있다.
• 파스칼의 삼각형은 2차원 배열과 그 2차원 배열을 할당하기 위한 2중 반복문이 필요하다.
• bottom-up 방식으로 구현하였다.
• 자주 출제될 수 있는 유형이다.

코드

# https://www.acmicpc.net/problem/16395
# boj, 16395: 파스칼의 삼각형, python3
import sys

input = sys.stdin.readline

def dp(n, k):
    # 앞서 계산된 결과를 저장하기 위한 dp 테이블 초기화
    d = [[1 for _ in range(i)] for i in range(1, 31)]

    # DP bottom-up
    for i in range(2, 30):
        for j in range(1, i):
            d[i][j] = d[i-1][j-1] + d[i-1][j]

    return d[n-1][k-1]

if __name__ == '__main__':
    n, k = map(int, input().split())

    print(dp(n, k))

결과

출처 & 깃허브

BOJ 16395
github