[BOJ/python] 1932: 정수 삼각형

문제

✔️ silver 1

문제 흐름

처음에는 memo를 1차원 배열으로 줄까지 온 경우 최대 값을 저장하도록 하려고 했는데,
그 다음 줄으로 넘어가면서 윗줄의 결과까지 전부 바뀌어버리는 경우도 존재하기 때문에 어떻게 해야할지 고민했었다.

그러다 GPT에게 힌트를 받고 memo를 triangle과 같이 2차원 배열로 정의해 각 최하층 값에서 큰 값을 구해가며 올라오는 식으로 진행했다.
시간복잡도가 O(n^2)으로 비효율적이라고 생각해서 전혀 고려하지 않은 방법이었는데, 1 <= n <= 500이기 때문에 이 방식으로 진행해도 크게 무리가 없었다.

무조건 O(n^2)은 너무 커! 가 아니고 제한사항을 확인한 뒤 파악하는 것도 꽤나 중요할 것 같다.

코드

# 정수 삼각형
# dp

import sys
input = sys.stdin.readline

def dp (t: list):
    n = len(t)
    if n == 1:
        return t[0][0]

    memo = [[0 for i in range(j + 1)] for j in range(n)]
    memo[n - 1] = t[n - 1]

    for i in range(n - 2, -1, -1):
        for j in range(i + 1):
            memo[i][j] = t[i][j] + max(memo[i + 1][j], memo[i + 1][j + 1])
    
    # print(memo)
    return memo[0][0]


if __name__ == "__main__":
    n = int(input())
    triangle = []
    for i in range(n):
        nums = list(map(int, input().split()))
        triangle.append(nums)
    result = dp(triangle)
    print(result)