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

programmers.co.kr/learn/courses/30/lessons/43105

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

 처음 보고 떠오른 생각은 굳이 2차원 벡터로 나타낸 이유가 뭐지?라는 생각이었다. 1차원 백터와 인덱스를 사용하여도 정수 삼각형을 만들 수 있는데. 2차원 벡터로 문제를 풀어야하나 보다.

 떠올린 풀이는 DFS. 구현을 했지만 시간 초과였다. 다른 방법을 찾아야 했다.

 

 2차원 벡터를 만들어, 해당 자리까지 도달하기 위한 최대값을 저장해놓으면 될 것 같았다. 이전 값으로 현재 값을 업데이트 하는 방식을 사용하였다. 다른 사람의 풀이를 보니 현재 값을 기준으로 다음 값을 업데이트하는 방법도 있었다. 이 방법이 코드가 더 깔끔하다.

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    vector<vector<int>> distance = triangle;
    // 0,0을 제외한 모든 값을 0으로 초기화
    for(int i=1; i<distance.size(); ++i)
        for(int j=0; j<distance[i].size(); ++j)
            distance[i][j] = 0;
    
    for(int i=1; i<triangle.size(); ++i){
        for(int j=0; j<triangle[i].size(); ++j){
            int left = 0;
            // 계산된 거리 백터에서 위-왼쪽값이 존재하면 업데이트
            if(triangle.at(i-1).size()>j){ left = distance.at(i-1).at(j); }
            
            // 계산된 거리 백터에서 위-오른쪽값이 존재하면 업데이트
            int right = 0;
            if(triangle.at(i-1).size()>j-1){ right = distance.at(i-1).at(j-1); }
            
            // 더 큰값과 현재 값을 더해줌
            int bigger = left>right? left:right;
            distance.at(i).at(j) = bigger + triangle.at(i).at(j);
        }
    }
    // 마지막 백터에서 제일 큰 값을 찾는다.
    int maxDistance = 0;
    for(int i: distance.at(distance.size()-1))
        if(maxDistance<i) maxDistance = i;
    
    return maxDistance;
}

 다른 풀이를 찾아보면, 벡터의 첫 번째와 마지막, 그리고 나머지 3 경우로 나누어 문제를 풀었다. 

 

 Time Complexity 테스트를 통과하지 못한 코드. DFS를 사용하였다.

#include <string>
#include <vector>
using namespace std;

int recursion(const vector<vector<int>>& triangle, int depth, int sum, int idx){
    if(depth==triangle.size()){ return sum; }
    
    int element = triangle.at(depth).at(idx);
    int isMax1 = recursion(triangle,depth+1, sum+element, idx);
    int isMax2 = 0;
    if(idx+1 < triangle.at(depth).size()){
        element = triangle.at(depth).at(idx+1);
        isMax2 = recursion(triangle,depth+1, sum+element, idx+1);
    }
    return isMax1>isMax2? isMax1: isMax2;
}
int solution(vector<vector<int>> triangle) {
    return recursion(triangle, 0,0,0);
}