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

프로그래머스

 

 

 

• 마지막 열에 거쳐간 숫자의 합의 최댓값들이 있어야함
• 2차원 배열을 만들어서 아래 열로 갈때마다 이 전 2개 칸 중 더 큰 값과 현재 칸의 값을 더한 값을 저장해나가면 됨
• 배열 [i][j]에는 [i-1][j-1], [i-1][j] 중 더 큰 값에 삼각형 [i][j]를 더한 값이 저장됨
• 점화식으로 나타내면 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
• 추가로 왼쪽과 오른쪽 끝에서는 아랫열에 칸이 하나 밖에 없으므로 이에 대한 처리를 해줘야함
• 수행이 끝난 뒤 마지막 열에서 최댓값을 찾아 리턴

 

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

using namespace std;

// DP 문제
// i 칸에서 i + 1 칸으로 이동할때 i 칸에서에서 j 번째 숫자는 i + 1 칸의 j 또는 j + 1번째 숫자로 이동 가능
// 거쳐간 숫자의 최댓값을 구하려면 [i][j]까지의 합들이 항상 최댓값이 되어야함
// 즉 [i][j]는 [i-1][j-1]과 [i-1][j] 중 큰 값에 원래 [i][j]에 위치한 값을 더한 값이 됨
// 점화식으로 나타내면 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];

// 이게 음수 인덱스가 되면 0으로 인식하게 되어있는건진 잘 모르겠는데 위에 점화식만 반복으로 돌렸는데 문제가 발생하지 않았다
// 그래도 음수 인덱스가 정상은 아니므로 왼쪽 끝과 오른쪽 끝에 대한 처리를 해주자
int dp[500][500];

int solution(vector<vector<int>> triangle) {
    int answer = -1;
    int height = triangle.size();
    dp[0][0] = triangle[0][0];
    
    for(int i = 1; i < height; i++) {
        for(int j = 0; j <= i; j++) {
            // 왼쪽 끝일 때
            if (!j) {
                dp[i][j] = dp[i-1][j] + triangle[i][j];
            }
            // 오른쪽 끝일 때
            else if (i == j) {
                dp[i][j] = dp[i-1][j-1] + triangle[i][j];
            }
            // 해당 없음
            else {
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }
    }
    
    for(int i = 0; i < triangle[height - 1].size(); i++) {
        answer = max(answer, dp[height - 1][i]);
    }
    
    return answer;
}