[백준 1932] 정수 삼각형

문제

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

1932번: 정수 삼각형

---

아이디어

가장 위층부터 아래층에 있는 두 수 중 하나를 선택해서 가장 아래층으로 가는 경로 중에서 합이 가장 큰 경우를 구하는 문제다. 문제 예제에서 최적의 경로부터 보면 다음과 같다.

 

 7
 3   8
 8   1   0

 2   7   4   4
 4   5   2   6   5

 

쉽게 생각하면, 가장 위층부터 시작해서 아래층으로 내려가면서 합을 구해보면 된다.

5층의 경우 양쪽으로 갈 수 있기 때문에 4층에 더해주면 다음과 같이 10, 15가 된다. 

또한 각 층의 가장 왼쪽은 그 윗층의 가장 왼쪽값만 더해줄 수 있고, 각 층의 가장 오른쪽은 그 윗층의 가장 오른쪽값만 더해줄 수 있기 때문에 다음과 같이 만들 수 있다. 

그러면 각 층에서 양쪽 끝이 아닌 곳의 값들은 어떻게 처리하면 될까.

3층의 1을 보면, 4층의 10 또는 15를 받을 수 있다. 당연히 더 큰 값을 받아서 커지는 게 좋다. 따라서 15를 받는다.

2층의 7, 4도 마찬가지다.

• 7은 18, 16 중에 하나의 값을 받을 수 있다. 따라서, 18을 받아서 25가 된다.
• 4는 16, 15 중에 하나의 값을 받을 수 있다. 따라서 16을 받아서 20이 된다.

2층의 7, 4도 마찬가지다.

• 5는 20, 25 중에 하나의 값을 받을 수 있다. 따라서, 25를 받아서 30이 된다.
• 2는 25, 20 중에 하나의 값을 받을 수 있다. 따라서, 25를 받아서 27이 된다.
• 6은 20, 19 중에 하나의 값을 받을 수 있다. 따라서, 20을 받아서 26이 된다.

실제로도 그렇게 계산이 되는지 확인해보자. 

제대로 계산이 된 것을 볼 수 있다. 따라서 1층에서 가장 큰 값인 30을 반환하면 된다.

---

Solution

n = int(input())

lst = []
for i in range(n) : 
    lst.append(list(map(int, input().split())))

for i in range(1, n) :  
    lst[i][0] += lst[i-1][0]
    lst[i][-1] += lst[i-1][-1]
    
    if i >= 2 :  
        for k in range(1, len(lst[i])-1) : 
            lst[i][k] += max(lst[i-1][k-1], lst[i-1][k])

print(max(lst[-1]))