백준(BOJ) 동적 프로그래밍 정수 삼각형 (1932) - Silver 1

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

문제 해결

경우의 수 + N값이 크다 => 동적프로그래밍

해당 문제를 보고 동적프로그래밍 접근 방법을 생각했다. 일단 순방향 계산을 하는 방식으로 접근했는데 충분히 해결 가능하다고 생각했다. 우선 정수삼각형 조건을 보면 값은 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 이 문제를 삼각형으로 보는 것 보다 예시처럼 2차원 배열로 보고 생각하면 더 쉽게 해결이 가능하다.

위와 같이 2차원 배열로 보면 대각선 왼쪽 오른쪽을 신경 쓸 필요 없이 왼쪽 대각선과 위만 신경쓰면 된다. 위 방식으로 2개의 규칙으로 해결하면 다음과 같다.

1. j ==0 인 경우 왼쪽 대각선이 존재하지 않으므로 그냥 자신의 위값만 더해주면 된다 (문제에서 음수는 없다고 했으므로 더하기만 해도 상관없음)

2. 왼쪽 대각선이 존재 하는경우 자신의 위의 있는 값과 대각선 왼쪽에 있는 값을 비교하여 더 큰값을 이용하여 최댓값을 갱신한다. 

이 방식을 사용하면서 테이블을 갱신하면 최댓값을 찾을 수 있다. 

삼각형을 그려서 접근하면 조금 어렵고 2차원 배열로 그러서 접근하면 쉽게 문제를 해결할 수 있는 문제였다.

 

전체 코드

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

typedef long long ll;

ll max_value(vector<vector<ll> >&dp){
    ll max_val = 0;
    for(ll i=0; i<dp.size(); i++){
        for(ll j=0; j<dp.size(); j++){
            if(max_val < dp[i][j]){
                max_val = dp[i][j];
            }
        }
    }
    return max_val;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r", stdin);

    ll n = 0;
    cin >> n;

    vector<vector<ll> >triangle(n, vector<ll>(n, 0));
    vector<vector<ll> >dp(n, vector<ll>(n, 0));
    for(ll i=0; i<n; i++){
        for(ll j=0; j<=i; j++)
            cin >> triangle[i][j];
    }
    dp[0][0] = triangle[0][0];
    for(ll i=1; i<n; i++){
        for(ll j=0; j<=i; j++){
            if(j==0){
                dp[i][j] = dp[i-1][j] + triangle[i][j]; // 자신의 위 + 자기 자신
            }
            else{
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) +  triangle[i][j]; // 왼쪽 대각, 자신의 위 중 큰 값 + 자기 자신
            }
        }
    }

    cout << max_value(dp) << "\n";
    return 0;
}