[Python] 1923 정수 삼각형

1923 정수 삼각형

[정답 코드]

n = int(input())
trianlge = []
for i in range(n):
    trianlge.append(list(map(int, input().split())))
for i in range(1, n):
    for j in range(len(trianlge[i])):
        if j == 0:
            trianlge[i][j] += trianlge[i - 1][j]
        elif j == len(trianlge[i]) - 1:
            trianlge[i][j] += trianlge[i - 1][j - 1]
        else:
            trianlge[i][j] += max(trianlge[i - 1][j], trianlge[i - 1][j - 1])
print(max(trianlge[n - 1]))

[풀이]
1149 RGB 거리 문제와 매우 유사하다.

문제의 조건 : '아래층으로 내려갈 때 왼쪽 대각선 or 오른쪽 대각선을 선택할 수 있다'

• 특정 칸까지의 최댓값을 구하고자 한다면, 바로 위층의 대각선 두 칸까지의 최댓값 중 큰 값을 가지고 내려오면 된다.
• 삼각형의 모서리에 해당하는 부분은 바로 위의 값을 그대로 가져온다.(if j == 0 and elif j == len(trianlge[i]) - 1)
• 동적 프로그래밍의 메모이제이션 기법으로 답을 계속 저장하면서 내려온 뒤 마지막 행에서의 최댓값이 최종 답이 된다.

[적용 자료구조 및 알고리즘]

• Dynamic Programming