백준 1932번: 정수 삼각형 C++코드(DP, 다이나믹 프로그래밍)

#include<iostream>
#include<vector>

using namespace std;

int arr[501][501];
int cost[501][501] = {0,};
int n;

void dp(){
    for(int i=0; i<n-1; i++){
        for(int j=0; j<=i; j++){
            if(cost[i+1][j] < cost[i][j] + arr[i+1][j]){
                cost[i+1][j] = cost[i][j] + arr[i+1][j];
            }
            if(j+1<n){
                if(cost[i+1][j+1] < cost[i][j] + arr[i+1][j+1]){
                    cost[i+1][j+1] = cost[i][j] + arr[i+1][j+1];
                }
            }
        }
    }
}

int main(){
    int temp;
    cin >> n;
    for(int i=1; i<n+1; i++){
        for(int j=0; j<i; j++){
            cin >> temp;
            arr[i-1][j] = temp;
        }
    }
    cost[0][0] = arr[0][0];
    dp();
    int max = 0;
    for(int i=0; i<n; i++){
        if(cost[n-1][i] > max){
            max = cost[n-1][i];
        }
    }
    cout << max;
}

설명

정수 삼각형을 이런식으로 보지 말고,

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

 

이런식으로 보는게 조금 더 편하다. 저것을 2차원 배열에 넣고 [y][x]에서 [y-1][x]와[y-1][x-1]로 메모이제이션을 활용해서 문제를 풀 수 있었다. cost라는 2차원 배열에 메모이제이션을 하고, cost[n-1]의 값 중에 가장 높은 값을 출력하면 된다.

 

문제점

dp 함수를 재귀로 만들었다가 시간초과 걸려서 반복문으로 바꿔주었다.