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

문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

 

동적계획법 문제이다!

 

 

입력에 triangle[0]에 원소 1개라고 나와있는데; 실제로는 데이터가 없는 위치에는 0으로 채워진 형식이다;;

 

문제 제대로 만들지...

 

 

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    vector<int> prev;
    vector<int> cur = triangle[0];
    
    for(int i = 1; i < triangle.size(); i++) {
        prev = cur;
        cur.assign(prev.size(), 0);
        
        
        cur[0] = triangle[i][0] + prev[0];
        
        for(int j = 1; j < cur.size() - 1; j++) {
            cur[j] = triangle[i][j] + max(prev[j - 1], prev[j]);
        }
        
        cur.back() = triangle[i].back() + prev.back();
        
    }
    
    for(const auto& el : cur) {
        if(el > answer) {
            answer = el;
        }
    }
    
    return answer;
}

 

 

 

개발 환경 : vscode

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