[프로그래머스] 정수 삼각형

---

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int n = triangle.size();
    
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < triangle[i].size(); j++) {
            triangle[i][j] += max(triangle[i + 1][j], triangle[i + 1][j + 1]);
        }
    }
    
    return triangle[0][0];
}

---

📝 풀이

삼각형의 가장 아래에서 두 번 째 줄부터 시작합니다.

바로 아래 줄의 두 칸 중 큰 값을 더하여 값을 갱신합니다.

 

아래에서 두번째 줄

 

• 현재 줄: [2, 7, 4, 4]
• 아래 줄: [4, 5, 2, 6, 5]

2 + max(4, 5) = 2 + 5 = 7

7 + max(5, 2) = 7 + 5 = 12

4 + max(2, 6) = 4 + 6 = 10

4 + max(6, 5) = 4 + 6 = 10

 

이 과정을  맨 윗줄까지 반복하면 꼭대기에 저장된 값이 최대 합이 됩니다.

따라서 triangle[0][0] 값을 return 합니다.