[백준] 1932번 : 정수 삼각형 (python 파이썬)

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

 

 

 

n = int(input())
dp_previous = []
for i in range(n):
  if i == 0:
    dp = list(map(int, input().split(" ")))
    dp_previous = dp
  else:

    dp = list(map(int, input().split(" ")))
    for j in range(len(dp)):
      if j == 0:
        dp[j] = dp[j] + dp_previous[j]
      elif j == len(dp)-1:
        dp[-1] = dp[-1] + dp_previous[-1]
      else:
        dp[j] = max(dp[j]+dp_previous[j-1], dp[j]+dp_previous[j])
    dp_previous = dp
    
print(max(dp))

 

이 문제는 전형적인 dp 문제 중 하나이다. 

 

dp(Dynamic Programmin) 문제 특성상 일련의 규칙에 따라 반복되는 특성을 가지고 있다.

 

이 문제에는 삼각형의 마지막 줄과 그 이전의 줄만 집중하면 된다. 

 

마지막 줄은 이전의 줄보다 +1 개의 수를 가지고 있을 것이다.

 

층이 내려갈 수록 대각선 왼쪽 또는 오른쪽만 선택할 수 있으므로, 이전 줄과 현재 줄의 합 중 최대를 구해 이를 갱신하가는 과정을 반복한 후, 마지막 줄에서의 최댓값을 출력하면 된다. 

 

 

예시)

이전 줄 :       OOOO

마지막 줄 :  OOOOO

 

이때 

1. 마지막 줄의 첫 번째 수는 무조건 이전 줄의 첫 번째 수와의 합이다. (빨강)

2. 마지막 줄의 마지막 수는 무조건 이전 줄의 마지막 수와의 합이다. (파랑)

3. 1과 2를 제외한 나머지의 경우 마지막 줄의 수는 이전 줄과 같은 번째의 수와의 합과 그 전번째 수와의 합 중 더 큰 값이다. (보라) 

 

3번을 더 자세히 알아보자

 

 

 

마지막 줄 :  OOOOO 의 세번째 숫자인 O를 예시로 들어보자

 

 

이 경우 이전 줄의 2번째 숫자와의 합과 3번째 숫자와의 합 중 더 큰 값이 될것이다. 

 

따라서 이전 줄 :  OOOO  의 보라색 부분인 2번째 숫자와 3번째 숫자와의 합 중 가장 큰 값을 마지막 줄의 3번째에 갱신하면 된다.