정수 삼각형

전형적인 DP 문제였다.

보자마자 DP 배열을 만들어서 최대값을 찾아나가면 될 것이라고 생각이 들었다.

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
	
    //D 벡터 사용 용이하도록 미리 할당
    vector<vector<int>> D(triangle.size());
    for (int i = 1; i < triangle.size()+1; i++)
    {
        D[i - 1].resize(i);
    }
	//
    
    //초기값 설정, 사이즈가 1이면 그냥 return
    D[0][0] = triangle[0][0];
    if (triangle.size() > 2)
    {
        D[1][0] = D[0][0] + triangle[1][0];
        D[1][1] = D[0][0] + triangle[1][1];
    }
    else
    {
        return D[0][0];
    }
    //

    //바텀 업 방식으로 최대값을 찾아나간다.
    for (int i = 2; i < triangle.size(); i++)
    {
        for (int j = 0; j < triangle[i].size(); j++)
        {
        	//삼각형 제일 왼쪽일 때
            if (j == 0)
            {
                D[i][j] = D[i - 1][j] + triangle[i][j];
            }
            //삼각형 제일 오른쪽 일 때
            else if (j == triangle[i].size()-1)
            {
                D[i][j] = D[i - 1][j - 1] + triangle[i][j];
            }
           	//대각선 왼쪽과 오른쪽 비교 후 큰 쪽을 선택
            else
            {
                D[i][j] = max(D[i - 1][j - 1] + triangle[i][j], D[i - 1][j] + triangle[i][j]);
            }
        }
    }
	
    //D벡터 마지막 줄에서 제일 큰 수 찾기
    for (int i = 0; i < triangle[triangle.size() - 1].size(); i++)
    {
        if (answer < D[triangle.size() - 1][i])
        {
            answer = D[triangle.size() - 1][i];
        }
    }

    return answer;
}

회고

어떻게 풀어야할지 바로 떠올라서 슥슥 했는데 계속 segmentation fault가 떠서 난감했다.
D를 편하게 쓰려고 맨 처음에 미리 할당을 해줬는데 여기서 실수가 있었다..
그것도 모르고 계속 바텀업을 진행하는 과정에 뭐가 잘못됐나 찾아보고 있었던 내 시간이 매우 아깝다 ㅜ

out of range를 항상 조심하도록 하자