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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

지나갈 수 있는 모든 경로를 재귀로 해결하면 O(2^n)으로 TLE가 발생한다.

dp 방법을 이용하여 O(n^2)에 해결해보자.

 

dp[i][j]를 triangle[i][j]에 도달할때까지의 최대 합이라고 설정하면,  dp[i][j]까지 도달하는 방법은 두가지가 있다.

1) (i-1, j-1)에서 오른쪽으로 내려오는 방법

2) (i-1, j)에서 왼쪽으로 내려오는 방법

 

따라서, dp[i][j]의 값은 dp[i-1][j-1]과 dp[i-1][j] 중 더 큰 값에 triangle[i][j] 를 더한 값이다.

점화식을 세워보면, dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] 가 된다.

 

모든 행에 대하여 dp 값을 구한 후, triangle.size()-1 행의 dp값 중 최대값을 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cctype>
#include <climits>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int dp[505][505];

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