[C++]동적계획법(Dynamic Programming) 정수 삼각형(프로그래머스 3레벨)

 
#include <string>
#include <vector>
 
using namespace std;
 
/*
0       0
01      1
012     2
0123    3
*/
 
int solution(vector<vector<int>> triangle)
{
    int answer = 0;
 
    for (int i = 1; i < triangle.size(); ++i)
    {
        for (int j = 0; j < triangle[i].size(); ++j)
        {
            if (j != 0 && j < triangle[i - 1].size())
                triangle[i][j] += max(triangle[i - 1][j], triangle[i - 1][j - 1]);
            else if (j == 0)
                triangle[i][j] += triangle[i - 1][j];
            else
                triangle[i][j] += triangle[i - 1][j - 1];
 
            if (i == triangle.size() - 1)
                if (answer < triangle[i][j])
                    answer = triangle[i][j];
        }
    }
 
    return answer;
}
 

처음에는 재귀함수로 DFS로 풀려고 했다. 근데 역시 바로 시간초과...

아래로 내려가면서 더 큰 수를 더해주는 형식으로 풀었는데

위로 올라가면서 더 큰수만 더해주는 형식이 더 좋을 것 같다.

프로그래머스에 다른 분이 푸신 게 있다.

if문을 하나 덜 거친다는 게 더 좋다..,

#include <string>
#include <vector>
 
using namespace std;
 
int solution(vector<vector<int>> t) {
    int answer = 0;
 
    for (int i = t.size() - 1; i > 0 ; i--)
    {
        for (int j = 0; j < t[i].size() - 1; j++)
        {
            if (t[i][j] > t[i][j + 1])
            {
                t[i - 1][j] += t[i][j];
            }
            else
            {
                t[i - 1][j] += t[i][j + 1];
            }
        }
    }
 
    answer = t[0][0];
 
    return answer;
}

효율성에 대해 좀 더 고민을 해봐야할꺼같다.