[이코테 Ch16-32] 정수 삼각형 (DP)

👩🏻‍💻문제설명

[이코테 Ch16-32] 정수 삼각형 (DP)

✍️Idea Sketch

문제요약

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

시간복잡도

O(n)

위에서부터 아래까지 모든 수를 한 번씩 탐색하므로 O(n)이다. 여기서 n은 순차탐색을 의미하며, 문제의 삼각형의 크기 n과는 다르다.

알고리즘 : 다이나믹 프로그래밍

✍️내 소스코드

• 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 따라서 dp[i-1][j]와 dp[i-1][j-1] 중 더 큰 값을 선택하면 된다.
• 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 이 때 가장 왼쪽에 있는 수는 대각선 왼쪽의 수가 없고, 가장 오른쪽에 있는 수는 대각선 오른쪽의 수가 없어 IndexError가 발생한다. 이 문제를 해결하기 위해 입력값 양쪽에 0 데이터를 추가하여 배열을 확장해준다.
• dp[i][0]의 경우 dp[i-1][0]는 탐색할 수 있지만 dp[i-1][-1]은 IndexError로 탐색할 수 없다. 그리고 dp[i][n-1]도 dp[i-1][n-1]은 IndexError로 탐색할 수 없지만 dp[i-1][n-2]는 탐색할 수 있다.

전체 코드

    import sys
    si = sys.stdin.readline

    n = int(si())
    dp = []
    for _ in range(n):
        arr = [0] + list(map(int, si().split())) + [0]
        dp.append(arr)

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

    print(max(dp[n-1]))