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

문제 설명

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

 

풀이

백준에서 풀어본 문제였기 때문에 코드는 금방 짰다. 그런데 자꾸 틀렸다고 나오길래 문제의 원인을 찾는데 애를 좀 먹었다. 문제는 triangle의 사이즈였다. 나는 triangle의 사이즈가 행별로 다를거라고 생각하고 코드를 짰는데 실제로 값을 확인해보니 triangle의 행별 사이즈는 모두 똑같았다. 이럴거면 입력값에 대해서 따로 말을 해주던지... 입출력 예만 보면 누가봐도 행별로 사이즈가 다를거라고 생각하지 않나..? 나만 그렇게 생각한건가? 아무튼 문제를 해결해서 좋긴 하지만 좀 허무하기도 하다.

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

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0, temp;
    int size = triangle.size();
    vector<vector<int>> dp(size);
    
    dp[0].push_back(triangle[0][0]);
    
    for(int i=1; i<size; i++) {
        for(int j=0; j< i + 1; j++) {
            if(j==0)
                temp = triangle[i][j] + dp[i-1][j];
            else if(j==i)
                temp = triangle[i][j] + dp[i-1][j-1];
            else
                temp = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j]);
            dp[i].push_back(temp);
        }
    }

    answer = *max_element(dp[size-1].begin(), dp[size-1].end());
    
    return answer;
}