정수 삼각형

📌문제

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

📌풀이

특정 위치로 도달하기 위해서는 1. 왼쪽 위, 2. 바로 위에서만 내려올 수 있음

모든 위치 기준으로 이전 위치로 가능한 2가지 위치까지의 최적의 합 중에 더 큰 합 가지는 경우 선택

 

📌코드

n = int(input())
dp = []

for _ in range(n):
    dp.append(list(map(int, input().split())))

for i in range(1, n):
    for j in range(i + 1):
        # 왼쪽 위에서 내려오는 경우
        if j == 0:
            up_left = 0
        else:
            up_left = dp[i - 1][j - 1]
        # 바로 위에서 내려오는 경우
        if j == i:
            up = 0
        else:
            up = dp[i - 1][j]
        # 최대 합 저장
        dp[i][j] = dp[i][j] + max(up_left, up)

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

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬