급하게임개발

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=cpp

이 문제는 프로그래머스 알고리즘 고득점 Kit의 문제이다 
Programmers LV3 문제 치고는 접근 법이 매우 쉬웠다 이 문제의 경우

이렇게 생긴 벡터가 제공이 된다 

실제 자료형은 이렇게 제공이 되는데
이 문제는 똑같은 삼각형을 만들고 나의 이전 행에 있는 나를 기준으로 양대각선의 있는 값중 나와의 합이 최대가 되는 애와의 합을 내가 현재 있는 위치에 넣는 것이다

즉 이그림을 보면 3번 째줄에 와서 보면 1을 기준으로 내가 선택할 수 있는 것은 이전행의 10과 15이다 이중 두값중 1과 합했을때 큰값을 16임으로 나의 위치에 16을 넣어준다 이를 계속 반복 해주면 된다

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> triangle) {
    vector<vector<int>> dpV;
    vector<int> rowV1;
    dpV.push_back(rowV1);
    dpV[0].push_back(triangle[0][0]);
    for(int i=1; i<triangle.size(); i++){
        vector<int> rowV;
        dpV.push_back(rowV);
        
        for(int j=0; j<triangle[i].size(); j++){
            if(j==0){
                dpV[i].push_back(dpV[i-1][j]+triangle[i][j]);
            }
            else if(j==triangle[i].size()-1){
                dpV[i].push_back(dpV[i-1][j-1]+triangle[i][j]);
            }
            else{
                dpV[i].push_back(max(triangle[i][j]+dpV[i-1][j-1],triangle[i][j]+dpV[i-1][j]));
            }
        }
    }
    int answer = 0;
    for(int i=0; i<dpV[triangle.size()-1].size(); i++){
        answer=max(answer,dpV[triangle.size()-1][i]);
    }
    return answer;
}

위에 코드를 보게 되면 똑같은 이차원 벡터를 만들어 주고 해당 벡터를 dp 로 놓고 이전 행과의 합을 계속 누적 하고 마지막행에서 최댓값을 구하는 방법으로 코드를 구현 했다