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

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

프로그래머스 코딩 테스트 고득점 Kit에 포함된 Level 3 DP 문제입니다.

[BOJ] 백준 1932번: 정수 삼각형과 동일한 문제입니다. (https://www.acmicpc.net/problem/1932)

 

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

using namespace std;

int tri[501][501], dp[501][501], n;

void init(vector<vector<int>>& triangle){
    for(vector<int> v : triangle){
        n = v.size();
        for(int i = 1; i <= n; ++i){
            tri[n][i] = v[i-1];
        }
    }
}

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    init(triangle);
    
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= i; ++j){
            dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + tri[i][j];
        }
    }
    answer = *max_element(dp[n], dp[n]+n+1);
    
    return answer;
}

 

백준 난이도 실버 1일 정도로 어렵지 않은 DP 문제입니다.

 

1) table 정의

dp[i][j] : i행 j열에 도달할 때 합이 최대가 되는 경로에 있는 수의 합

 

2) 점화식 찾기

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + tri[i][j];

 

3) 초기값 설정

1-based index를 사용하여 i = 0 or j = 0 부분이 경계치 역할을 하여 따로 추가해야 할 초기값 설정을 굳이 해주지 않아도 됩니다.

 

다만 백준에서는 입력값에 대해 바로 원하는 자료구조로 옮기면 됐지만, 프로그래머스에서는 미리 입력값을 넣은 자료구조를 주기 때문에 이를 사용하기 편한 형태로 변형하는 init() 과정이 필요한 점이 다소 불편하다고 느끼고 있습니다.