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

< 해설 >

동적 계획법 첫 문제다. 첫 문제이니만큼 동적계획법이란 어떤 상황에서 사용하는 것인지, 동적 계획법을 사용하지 않았을 때는 어떤 문제가 있는지 알아보기 위해서 먼저 기존에 사용하던 방식대로 코드를 짜 봤다.

아래는 동적 계획법을 사용하지 않고 재귀로 푼 풀이 방법이다. (코드는 제일 아래) 답은 올바르게 나온다. 다만 실행결과가 다음과 같다.

재귀를 통해 모든 노드에 대한 결과값을 얻고 sort 한 뒤 제일 앞에 있는 수를 얻은 결과이다. 

 

이제 왜 동적 계획법을 사용해야하는지 알았으니 동적 계획법을 적용시켜서 문제를 풀어보았다.

내가 사용한 방법은 Bottom-up 방식이다. 보통 이런 그래프에서 자주 사용하는것 같았다. 기존에 위에서 아래로 탐색하던 방법이 아니라 아래에서 위로 탐색하는 방식이다.

크게 다를거 없지 않나? 하고 생각할 수 도 있는데 해결하는 방식이 재귀가 아닌 전체 노드를 한번만 순회하여 답을 얻는다는 방식이 조금 다르다. 아래에서 위로 탐색해 가면서 작은 수는 탈락시킨다.

그림으로 설명하면 다음과 같다.

위는 가장 아래줄에 Bottom-up 방식을 적용한 것이다.

최종적으로는 아래의 그림과 같아진다.

새로운 개념을 적용시키는 문제는 시간이 많이 걸리고 어려웠는데 문제 자체의 난이도는 어렵지 않아서 동적 계획법을 처음으로 사용하는 문제로는 좋은 문제였던것 같다!

 

< 문제 >

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

 

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

 

 

< 풀이 >

동적 계획법 사용 x

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> vec_answers;

void Search(vector<vector<int>> triangle, int addNum, int curIDX, int cur_level, const int end_level)
{
    if(cur_level == end_level)
    {
        vec_answers.push_back(addNum);
        return;
    }
    
    Search(triangle, addNum + triangle[cur_level][curIDX], curIDX, cur_level+1, end_level);
    Search(triangle, addNum + triangle[cur_level][curIDX+1], curIDX + 1, cur_level+1, end_level);
}

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    Search(triangle, triangle[0][0], 0, 1, triangle.size());
    
    sort(vec_answers.begin(), vec_answers.end(), greater<int>());
    
    return vec_answers[0];
}

 

동적 계획법을 사용한 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    // Bottom-up 방식을 사용하여 아래부터 탐색.
    for(int i = (triangle.size()-2); i > 0; i--)
    {
        for(int j=0; j<triangle[i].size(); j++)
        {
            triangle[i][j] += max(triangle[i+1][j] , triangle[i+1][j+1]);
        }
    }
    triangle[0][0] += max(triangle[1][0] , triangle[1][1]);

    return triangle[0][0];
}

동적 계획법 유무 비교

<- 유                          무->