[PS] 정수 삼각형

문제

프로그래머스

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때,

거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하기

 

풀이

첫번째 층부터 마지막 층까지 거쳐온 모든 수를 더해서 계산해서 최댓값을 구하면 된다.

첫번째 층의 수에서 두번째 층(다음 층)의 수를 더해서 최댓값을 구하는 것이므로,

중복되는 부분 문제이고 이는 dp로 풀어야 함을 알 수 있다.

 

1. 점화식 구하기

아래의 입출력 예제를 통해 살펴보자.

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

1. 첫번째 줄

7부터 시작해서 하나씩 아래로 내려가보자.

 

2. 두번째 줄

3의 경우에는 7과 더해서 10,

8의 경우에는 7과 더해서 15

 

3. 세번째 줄

8의 경우에는 10과 더해서 18,

1의 경우에는 10과 15중 더 큰 수인 15와 더해서 16,

0의 경우에는 15가 된다.

 

 

현재 층의 위치에서 현재까지 지나온 누적 값은

이전 층의 원소 좌, 우 중 최댓값과 연관이 있으므로

아래와 같은 점화식을 세울 수 있다.

dp[i][j] = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j]) (j != 0 이고 j != i)
dp[i][j] = triangle[i][j] + dp[i-1][j] (j == 0)
dp[i][j] = triangle[i][j] + dp[i-1][j-1] (j == i)

 

j에 따라 dp식이 달라진다.

현재 위치가 맨 앞 (인덱스 0)인 경우에는 더 좌측 원소가 없으므로 자동으로 우측 원소 선택,

현재 위치가 맨 뒤 (인덱스 최대)인 경우에는 더 우측 원소가 없으므로 좌측 원소를 선택한다.

 

2. 누적 최댓값을 모두 구해야 하는 이유 (참고)

처음에는 초반 최댓값이 끝까지 최댓값을 유지할 거라 생각했다.

그러면 모든 경우의 수를 계산할 필요가 없다.

하지만 이런 경우 직접 그려본다면..

안된다는 것을 알 수 있다.

 

코드

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

int solution(vector<vector<int>> triangle) {
    int size = triangle.size();
    vector<vector<int>> dp(size, vector<int>(size, 0));
    dp[0][0] = triangle[0][0];
    
    for (int i = 1; i < size; i++){
        for (int j = 0; j <= i; j++){
            if (j == 0){
                dp[i][j] = triangle[i][j] + dp[i-1][j];
            } else if (j == i){
                dp[i][j] = triangle[i][j] + dp[i-1][j-1];
            } else {
            dp[i][j] = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j]);
            }
        }
    }
    
    // 마지막 층에서 최댓값 구하기
    int maxNum = 0;
    for (int k = 0; k < size; k++){
        maxNum = max(maxNum, dp[size-1][k]);
    }
    
    return maxNum;
}

 

마지막 층에서 최댓값을 구할 때, 범위가 dp[size][k]가 아닌 dp[size-1][k]임에 주의한다.

 

회고

디피 문제가 생각보다 쉬울 지도 모른다는 행복한 생각을 하게 해주는 문제였다.

구현하는건 어렵지 않은데 규칙을 찾고 점화식을 세우는데 시간이 꽤나 걸리는 듯 하다.