[알고리즘 일기 - 파이썬] 185. 정수 삼각형

문제 185. (2022-02-15)

 

1932번: 정수 삼각형

Baekjoon 1932. 정수 삼각형

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 

---

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

 

---

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

 

---

입력 예시

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

 

---

출력 예시

30

 

---

❧ 정답

🔎IDEA) DP - 이전 층의 최댓값을 더해주며 맨 위층에서부터 맨 아래층까지 순차적으로 내려온다.

[Line 6 - 9]
👉 triangle에 입력값을 받아서 리스트를 만들고 dp에 한줄 개수대로 dp 테이블을 만든다.

[Line 12 - 19]
👉 입력받은 정수 삼각형의 맨 위 노드에서 맨 아래 노드로 값을 순회하며 윗 줄에서 더 높은 값을 더하면서 삼각형을 내려온다.
👉 left 에는 위층의 좌측 원소 값을 넣고 right에는 위층의 우측 원소 값을 넣는다.
👉 이후 left와 right의 값을 비교하여 두 값 중 더 큰 값과 현재 노드의 값을 더해주며 dp 테이블에 값을 넣어준다.