[백준 1932] 알고리즘 41일차 : 정수 삼각형

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

1932번: 정수 삼각형

동적계획법 C++

숫자 트리에서 숫자들의 합이 최대가 되는 경로 구하기(최댓값 출력)

 

접근방법

전형적인 DP 상향식 풀이로 풀었다.

가장 밑 행부터 모든 숫자에 대해 해당 자리까지의 최댓값을 저장해가면서 값을 갱신한다.

예를들어 위의 사진에서 4번째 행 첫번째 자리 2에서 최댓값을 가지려면 4,5중 5를 선택해야하니까

원래 2가 있던 자리에 2+5 = 7을 저장한다. 두번째 자리인 7도 마찬가지로 5,2중에 5를 선택해서 7+5 = 12를 저장한다.

그렇게 맨 위까지 반복하면 결국 첫행 첫열에는 최댓값이 저장되게 된다.

 

이번 문제는 로직 정리하고 바로 코드 작성해서 완료까지 20분 정도 밖에 안걸렸다.

로직 정리하는데에도 그렇게 시간이 걸리진 않아서 굉장히 빨리 푼 것 같다.

전형적인 DP 풀이로 풀이되는 문제라 그런 것 같다.

 

소스코드

 

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    int integers[500][500];
    
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j <= i ; j++){
            cin >> integers[i][j];
        }
    }
    for(int i = n-2 ; i >= 0 ; i--){
        for(int j = 0 ; j <= i ; j++){
            integers[i][j] += max(integers[i+1][j], integers[i+1][j+1]);
        }
    }
    cout << integers[0][0];
    return 0;
}