[다이나믹 프로그래밍] 1932번 - 정수 삼각형

[백준] 1932번 - 정수 삼각형https://www.acmicpc.net/problem/1932

(한줄평) 익숙한 dp 문제라 쉽게 풀 수 있었던 문제!

풀이 시간: 10분 이내

유사 문제: 1149

https://hseungyeon.tistory.com/298

[다이나믹 프로그래밍] 1149번 - RGB거리

 

1) 문제 해결 아이디어

이 문제는 삼각형 크기 n(1이상 500이하)인 정수삼각형이 입력으로 주어질 떄 각 행에서 1개씩 값을 선택하여 만들어지는 합의 최댓값을 구하는 문제다.

여기서 주의해야할 점은 왼쪽 대각선, 오른쪽 대각선이지만 실제로 2차원 리스트에서 보면 현재 열이 j라고 했을 때 왼쪽 대각선은 (j - 1), 오른쪽 대각선은 j이다. 왼쪽 대각선(j-1)값이 0보다 작은 값일 때, 오른쪽 대각선(j)가 (i-1)보다 커질 때 예외처리를 해주어야 한다! 그렇지 않으면 IndexError가 난다.

<점화식>

2) 소스코드

n = int(input())  # 삼각형 크기(1이상 500이하)
d = [list(map(int, input().split())) for _ in range(n)]

for i in range(1, n):
  # 행의 크기만큼 반복
  for j in range(i + 1):
    # 왼쪽 대각선 값
    if j - 1 < 0: left_up = 0
    else:  left_up = d[i - 1][j - 1]
    # 오른쪽 대각선 값
    if j >= i: right_up = 0
    else:  right_up = d[i - 1][j]
    # 왼쪽 대각선 값&오른쪽 대각선 값 중 큰 값 선택
    d[i][j] += max(left_up, right_up) 

print(max(d[n - 1]))  # 합이 최대가되는 경로에 있는 수의 합