백준)정수 삼각형

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

1932번: 정수 삼각형

 

 

 

a = int(input())

arr = []

for i in range(a):
  arr.append(list(map(int,input().split())))


for i in range(1,len(arr)):
  for j in range(len(arr[i])):
    left = 0
    right = 0
    if j - 1 >= 0:
      left = arr[i-1][j-1] + arr[i][j]
    if len(arr[i -1]) > j:
      right = arr[i-1][j] + arr[i][j]
      

    arr[i][j] = max(left,right)

print(max(arr[-1]))

우선 DP문제이다.

문제는 각 트리 노드에서 대각아래 좌, 대각아래 우에만 더할 수 있으며, 각 트리를 지나 만들 수 있는 최대값을 구하는 문제이다.

 

무선 이 문제가 다이나믹 프로그래밍으로 푼 이유를 살펴보자.

물론 백준 사이트에 연관 알고리즘 'DP'라고 나오긴 했으나,

연관 알고리즘이 나오질 않았다면, 그리디도 생각해 보았을 것이다.

 

그러나 이 문제는 그리디로 풀 지 못한다.

그리디는 현재 주어진 조건에 만족하는 최대값만을 선택해 정답을 만들어나가는 알고리즘인데,

이 문제는 주어진 조건에 만족하는 최대값만 고른다면 트리를 최종적으로 지나 만들 수 있는 최대값을 놓칠 수 있기 때문이다.

 

예를들어 예시 문제를 보자.

예시문제는

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

이다.

이 트리에서 조건을 만족하며 그리디 알고리즘을 사용하면,

7 + 8 + 1 + 7 + 5 =. 28이된다.

하지만 문제에서 얻을 수 있는 최대값은

7 + 3 + 8 + 7 + 5 =. 30이다.

 

다음으로 코드를 보자.

코드는 간단하다.

자신이 더할 수 있는 값들 중 최대값으로 갱신해주는 코드이다.

첫번째 반복문을 보자

첫번째 반복문은 1부터 시작해 리스트의 끝까지,

두번째 반복문은 리스트의 i번째를 하나하나 확인하며 값을 갱신해나간다.

노드에서 더할 수 있는 값은 좌,우 두개 이므로 i-1번째의 j와 j-1을 비교해 더 큰값을 갱신시켜준다.