백준 1932번 숫자삼각형

문제 링크입니다: https://www.acmicpc.net/problem/1932

동적계획법을 사용하면 쉽게 풀 수 있는 문제입니다.

/*

숫자로 이루어진 삼각형에서 맨 위층부터 시작해 아래에 있는 수 중

하나를 선택하며 아래층으로 내려올 때, 최대합을 반환하시오

*/

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

int triangle[501][501]; //삼각형

int cache[501][501];

int N;

 

int maxSum(int stage, int idx) //층과 인덱스

{

        int &result = cache[stage][idx];

        if (result != -1)

               return result;

        if (stage == N - 1) //맨 아랫줄

               return result = triangle[stage][idx];

        return result = max(maxSum(stage + 1, idx), maxSum(stage + 1, idx + 1)) + triangle[stage][idx]; //↙ ↘ 둘 중 큰 쪽으로 이동

}

 

int main(void)

{

        cin >> N;

        if (N < 1 || N>500)

               exit(-1);

 

        for (int i = 0; i < N; i++)

               for (int j = 0; j <= i; j++)

                       cin >> triangle[i][j];

        memset(cache, -1, sizeof(cache));

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

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~