[동적계획법] 3. 삼각형 위의 최대 경로

https://algospot.com/judge/problem/read/TRIANGLEPATH

algospot.com :: TRIANGLEPATH

 

컨셉

점화식을 만들었다.

path(y,x)  //(y,x)에서 시작하여 맨 아래줄까지 내려가는 부분 경로의 최대합

path(y,x) = triangle(y,x) + max(path(y+1, x+1), path(y+1, x))

 

 

최적부분구조 ;

- 각 부분문제의 최적해 확장 → 전체 문제의 최적해 得

- 지금까지의 선택이 영향을 미치지 않음. 현재 상황에서 최적해를 선택한다

- 중복되는 핵심문제만 추출해야 한다. (계산결과에 영향을 미치는 애들)

- 핵심문제가 아닌 부분 or 어떤 루트를 타든 공통된 부분은 점화식 밖으로 빼버린다. (triangle(y,x)처럼)

 

 

초안

내가 짠 코드 (정답, 28ms)

/**
 * @name    8.3.삼각형 위의 최대 경로
 * @ID      TRIANGLEPATH
 * @date    2019-08-06
 * @author  Sunmon
 */

#include <iostream>
#include <cstring>
#define MAX(a,b) ( a>b ? a: b)
using namespace std;


int N, triangle[100][100], cache[100][100];

//(y,x)부터 바닥까지 내려가는 부분 경로의 최대 합 리턴
int path(int y, int x)
{
    if(y == N-1) return triangle[y][x];

    int& ret = cache[y][x];
    if(ret != -1) return ret;

    return ret = MAX(path(y+1, x), path(y+1, x+1)) + triangle[y][x];
}

int main()
{
    int C;
    cin >> C;
    while(C--)
    {
        memset(cache, -1, sizeof(cache));
        memset(triangle, -1, sizeof(triangle));
        cin >> N;
        
        for(int i = 0; i< N; i++)
            for(int j = 0; j<= i; j++)
                cin >> triangle[i][j];

        cout << path(0,0) << endl;

    }
}

 

주의

초기화 꼭 할 것