[고득점Kit][DP] 정수 삼각형 ⭐⭐⭐

[DP] 정수 삼각형

난이도 ⭐⭐⭐

문제

꼭대기 꼭짓점부터 트리 타고 내려오듯이 한 줄씩 내려온다. 자신을 기준으로 왼쪽 혹은 오른쪽 대각선을 타고 내려온다.

내 풀이 ⭕

동적계획법 알고리즘을 공부하고난 후, 이를 사용하여 내 힘으로 풀어낸 첫 DP 문제였다. 정답 받아서 기분이 좋았다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    vector<vector<int>> dp(triangle.size());
    
    // 초기값 (삼각형 밑변)
    for(int i = 0; i < triangle.size(); i++)
        dp.back().push_back(triangle.back()[i]);
    
    // DP
    for(int i = triangle.size() - 2; i >= 0; i--)
    {
        for(int j = 0; j <= i; j++)
            dp[i].push_back(max(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]);
    }
        
    answer = dp[0][0];
    return answer;
}

점화식 👉 현재 삼각형의 꼭짓점 숫자의 합 최대값 = Max [ 왼쪽 자식을 꼭짓점으로 한 삼각형의 숫자의 합 최대값, 오른쪽 자식을 꼭짓점으로 한 삼각형의 숫자의 합 최대값 ] + 현재 삼각형의 꼭짓점 수

맨 위 꼭짓점인 7 에서 왼쪽 오른쪽 자식들 중 어떤 것을 각각 선택하면서 타고 내려가야 얼만큼의 최대값을 합산해낼 수 있는지를 구해야 한다. 동적 계획법에 맞게 점화식을 세워 보자면 위와 같다. 삼각형 밑변인 아래에서 부터 Bottom-Up 방식으로 타고 올라가면서 dp 배열에 값을 저장해나간다. 우선 삼각형 밑변을 나타내는 dp의 마지막 행들이 초기값이 되므로 이들은 각각 자기 자신으로 값을 설정하여 넣어준다.

• triangle[4] : [4, 5, 2, 6, 5]
  • dp[4] 👉 [4, 5, 2, 6, 5]
• triangle[3] : [2, 7, 4, 4]
  • dp[3] 👉 [Max(4, 5) + 2, Max(5, 2) + 7, Max(2, 6) + 4, Max(6, 5) + 4] = [7, 12, 10, 10]
• triangle[2] : [8, 1, 0]
  • dp[3] 👉 [Max(7, 12) + 8, Max(12, 10) + 1, Max(10, 10) + 0] = [20, 13, 10]
• triangle[1] : [3, 8]
  • dp[3] 👉 [Max(20, 13) + 3, Max(13, 10) + 8] = [23, 21]
• triangle[0] : [7]
  • dp[4] 👉 [Max(23, 21) + 7] = [30] ✨정답✨

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기