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

안녕하십니까. Eun🦆입니다.

풀이법 입니다.

 

코딩테스트 연습 - 정수 삼각형

[시간 초과, DFS로 푼 코드]
// 처음 DFS로 완벽하게 풀었다고 좋아했는데... 아쉬운 결과
#include <string>
#include <vector>
using namespace std;
int answer = 0;
void DFS(vector<vector<int>> triangle, int sum, int y, int x)
{
    if(y>=triangle.size()-1)
    {
        if(sum > answer)
            answer = sum;
        
        return;
    }
    
    DFS(triangle, sum+triangle[y+1][x], y+1, x);
    DFS(triangle, sum+triangle[y+1][x+1], y+1, x+1);
}
int solution(vector<vector<int>> triangle) {
    DFS(triangle, triangle[0][0], 0, 0);
    return answer;
}
​
[DP]
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> triangle) {
    int answer = 0;
    vector<vector<int>>sav(triangle.size(),vector<int>(triangle.size()));
    // sav[y][x]
    for(int y=1;y<triangle.size();y++)
    {
        for(int x=0;x<=y;x++)
        {
            // sum을 저장하는 vector 생성?
            // for문에 들어가는 y와 x를 그대로 vector문을 만들수 있다
            if(x==0)
                sav[y][x] = sav[y-1][x] + triangle[y][x];
            else if(x==y)
                sav[y][x] = sav[y-1][x-1] + triangle[y][x];
            else
                sav[y][x] = max(sav[y-1][x]+triangle[y][x], sav[y-1][x-1]+triangle[y][x]);
            
            if(sav[y][x]>answer)
                answer = sav[y][x];
        }
    }
    return answer+triangle[0][0];
}

네이버 블로그 리뉴얼입니다.

(https://blog.naver.com/unsuk1/221996197718)