백준 1932 - 정수 삼각형 [C/C++]

1932번: 정수 삼각형 (acmicpc.net)

1932번: 정수 삼각형

문제 설명 / 입력 / 출력

예제 입력 / 예제 출력

 

보다 간단한 실버1 문제이다. 

보자마자 Dynamic Programming로 풀면 몇 줄 안에 금방 짜질 것 같아서 그렇게 짰고, 1트만에 풀었다.

 

내가 생각한 알고리즘은 다음과 같다.

• 어차피 내 바로 위의 부모 2개의 노드 값 + 현재 값으로 비용을 체크할 것이다.
• 그렇다면 그냥 DP로, 내 현재 값 + 내 부모 중 한 명 값 을 두 번 계산해서 max값을 내놓는다면? 그게 답이 될 것이다.
• 여기서 고려할 점은, 입력받은 삼각형 안의 값들을 in-place하게 바꾸어주어도 문제가 되지 않는다는 점이다.

제출한 C++ 코드는 다음과 같다.

#include <iostream>
#include <algorithm>
#include <vector>
#define fastcpp ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
int n;
vector<int> dp[501];
int main() {
    fastcpp;

    cin >> n;
    for (int i=1;i<=n;i++){
        for (int j=0;j<i;j++) {
            int dap;
            cin >> dap;
            dp[i].push_back(dap);
        }
    }
    if (n==1) cout << dp[1][0];
    else{
        int ans = 0;
        for (int i=2;i<=n;i++){
            int len = dp[i-1].size();
            for (int j=0;j<dp[i].size();j++){
                int maxV = -1;
                if (j-1>=0) maxV = dp[i][j]+dp[i-1][j-1];
                if (j<len) maxV = (maxV==-1) ? dp[i][j]+dp[i-1][j] : max(maxV,dp[i][j]+dp[i-1][j]);
                dp[i][j] = maxV;
                ans = max(ans, maxV);
            }
        }
        cout << ans;
    }

    return 0;
}