프로그래머스 LV3 - 정수 삼각형

0️⃣ 문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

1️⃣ 나의 풀이

동적 프로그래밍을 이용해 삼각형의 위에서 부터 저장해나가면서 왼쪽 오른쪽으로 나아간다.

left = dp[f][i] + triangle[f + 1][i];

right = dp[f][i] + triangle[f + 1][i + 1];

이런식으로 나아갔다. 그리고 그전에 dp에 저장 되어있는 원소와 비교하여 큰 값을 저장하는 식으로 진행했다.

2️⃣ 내 코드

#include <string>
#include <vector>
 
using namespace std;
 
int dp[500][500];
 
int solution(vector<vector<int>> triangle) {
    int answer = 0;
    size_t floor = triangle.size();
 
    dp[0][0] = triangle[0][0];
    size_t left = 0;
    size_t right = 0;
    for (size_t f = 0; f < floor - 1; f++) // 총 층의 -1번까지
    {
        for (size_t i = 0; i <= f; i++) //해당층의 원소 갯수만큼
        {
            //왼쪽으로 
            left = dp[f][i] + triangle[f + 1][i];
            if (left > dp[f + 1][i]) //기존값보다 크다면 고침
                dp[f + 1][i] = left;
 
            //오른쪽으로
            right = dp[f][i] + triangle[f + 1][i + 1];
            if (right > dp[f + 1][i + 1]) //기존값보다 크다면 고침
                dp[f + 1][i + 1] = right;
        }
    }
    
    for (int i = 0; i<floor; i++)
    {
        if (answer < dp[floor - 1][i])
            answer = dp[floor - 1][i];
    }
 
    return answer;
}

 기억 할 점

dp의 자료형을 제대로 만들지 않아 고생했다.

자료형 설정에 좀 더 신중하자