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

문제 설명

 

 

-------------------------------------------------------------------------------------------------------------------------------------------

 

문제풀이

 

1. 문제를 풀 수 있는 방법은 DFS 알고리즘과 DP 알고리즘이 떠올랐다. 

   하지만 이 문제는 최종 최댓값만을 원하므로 DP 알고리즘이 시간복잡도 면에서 더 좋다 생각하여 

   DP 알고리즘으로 풀게 되었고, 또한 DP 알고리즘 특성상 이전 값의 계산한 결과를 저장해두고 동일한 부분 문제가 다시 등장할

   때 재 사용함으로써 중복 계산을 제거할 수 있기 때문인 이유도 있다.

 

2. 즉, 이전 메모리 값을 활용하면 좋은 문제임을 알아서 다음 단계로 해당 값을 어떠한 방식으로 저장할지는 

   맨 첫번째 요소와 끝요소는 상위 행의 같은 인덱스값을 참고하고 나머지는 양 옆을 확인하도록 코드를 구성했다.

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------

 

코드

#include <string>
#include <vector>

using namespace std;


// 위에서 바닥까지 가는 경로중 가장 숫자의 합이 큰 경우의 수 찾기 

int solution(vector<vector<int>> triangle) 
{
    int answer = 0;
 
    for(int i=0; i<triangle.size()-1; i++) // vector.size() = 삼각형의 높이
    {
        int upper_size = triangle[i].size();
        int down_size = triangle[i+1].size();
        
        for(int j=0; j<down_size; j++)
        {
            if(j == 0 )
                triangle[i+1][0] += triangle[i][0];
            
            else if(j == down_size - 1)
                triangle[i+1][down_size - 1] += triangle[i][upper_size - 1];
            
            else
            {
                triangle[i+1][j] = max( (triangle[i+1][j] + triangle[i][j-1]),
                                       (triangle[i+1][j] + triangle[i][j]));
            }
        }
        
    }
    
    
    for(auto& iter: triangle[triangle.size()-1])
    {
        answer = max(answer,iter);
    }
    

    return  answer;
}