프로그래머스: 정수 삼각형⭐⭐⭐

난이도 ⭐⭐⭐

🧐 문제

문제 설명

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

---

🔍 힌트

7
3	8
8	1	0
2	7	4	4
4	5	2	6	5

삼각형의 형태를 왼쪽 정렬된 형태로 구현하면 편하게 구현할 수 있다.

하지만 DP를 사용하려면 코드의 흐름이 위쪽에서 아래로 가는 것보단 아래에서 위쪽으로 가는 형태로 짜는 것이 더 좋을 것이다.

4	5	2	6	5
2	7	4	4
8	1	0
3	8
7

---

✏️ 나의 풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> dp (500, vector<int>(500));

int solution(vector<vector<int>> triangle) {
    int size = triangle.size();
    
    dp[0] = triangle[0];
    for(int i=0; i<size-1; i++) {
        for(int j=0; j<triangle[i].size(); j++) {
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + triangle[i+1][j]);
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + triangle[i+1][j+1]);
        }
    }
    
    vector<int> result = dp[size-1];
    sort(result.begin(), result.end(), greater<int>());
    
    return result[0];
}

✔️ 다른 사람의 풀이

#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;
}

🧐 분석

이전에도 이와 비슷한 DP문제를 풀어본 적이 많았기에 이번에는 위에서 아래로 내려오는 구조로 풀어보았다. 이러한 구조로 풀어보니 단점이 확실히 드러났다.

1. DP 배열을 따로 선언해주어야 한다.
2. max 함수를 한번이 아닌, 두번 써야한다.
3. sort하여 가장 큰 값을 또 다시 구해주어야 한다.

이렇게 풀어보니 DP 문제에 대한 접근 방식이 중요하다는 것을 느낄 수 있었다.

Programmers 카테고리 내 다른 글 보러가기