(C++) - 프로그래머스(고득점 kit - 동적계획법(DP)) : 정수 삼각형 답

programmers.co.kr/learn/courses/30/lessons/43105

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

간단한 dp문제였습니다.

 

 

풀이방법

 1. d배열을 정의합니다

 현재 i층의 j번째 원소가 최적의 방법으로 선택했을 때의 최대값 : max(i-1번째 층 j-1원소, i-1 번째 층 j원소) + 삼각형 i층 j번째 원소의 값

 

 2. 마지막 층의 d의 원소들 중 최대값을 반환합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;

int solution(vector<vector<int>> triangle) {
    int size = triangle.size();
    int answer = 0;
    int d[501][501];
    memset(d,0,sizeof(d));
    for(int i = 1; i <= size; i++)
        for(int j = 1; j <= triangle[i-1].size(); j++)
            d[i][j] += max(d[i-1][j-1],d[i-1][j]) + triangle[i-1][j-1];
    for(int i = 1; i <= triangle[size-1].size(); i++)
        answer = max(answer, d[triangle[size-1].size()][i]);

    return answer;
}

int main(){
    vector <vector<int>> triangle;
    triangle.push_back({7});
    triangle.push_back({3,8});
    triangle.push_back({8,1,0});
    triangle.push_back({2,7,4,4});
    triangle.push_back({4,5,2,6,5});
    cout << solution(triangle);
}