[DP] 정수 삼각형

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 20분

1. 문제 설명

- 정수값으로 이루어진 행렬이 삼각형 모양으로 주어질 때, 위에서 아래로 내려가며 각 위치의 값을 더해갈 때 최대가 되는 값은 무엇인지 묻는 문제

2. 접근 방식

- 점화식을 세워서 문제를 풀었다. (dp[i][j] = triangle[i][j] + max(dp[i-1][j], dp[i][j]))
- i의 조건을 체크해줘야 된다. i가 없으면 0이어야 한다. 

3. 코드

n = int(input())

triangle = []

for _ in range(n):
    triangle.append(list(map(int, input().split())))
    
dp = []
for i in range(1, n+1):
    dp.append([0]*i)
dp[0][0] = triangle[0][0]

for i in range(1, n):
    for j in range(len(triangle[i])):
        up_left = 0 if j == 0 else dp[i-1][j-1]
        up_right = 0 if j == len(triangle[i])-1 else dp[i-1][j]
        dp[i][j] = triangle[i][j] + max(up_left, up_right)
print(max(map(max, dp)))

4. 코멘트

- max(map(max,dp)): 2차원 배열의 원소 중 최대값을 출력하는 좋은 코드인 거 같다. 기억해놓자.

- 점화식을 세우고 문제를 푸니까 훨씬 수월했던 것 같다.