정수 삼각형

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

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

#include <string>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int n = triangle.size();
    int check[500][500];
    memset(check,0,sizeof(check));
    check[0][0] = triangle[0][0];
    

    for(int i=1; i<n; i++){
        for(int j=0; j<=i; j++){
        int first =0;
        if(j>=1){
         first=check[i-1][j-1]+triangle[i][j]; //바로위에서 왼쪽꺼랑 현재 위치꺼랑 더한것
        }
        int second =0;
        if(j<=i-1){
         second = check[i-1][j] + triangle[i][j];//바로 위에꺼랑 현재위치꺼랑 더한것
        }
            check[i][j] = max(first,second);  // 둘중 더 큰 것을 저장, 메모이제이션 기법
            //cout<<check[i][j]<<" ";
          
        }
     //   cout<<endl;
    }
    
    int maxnum =0;
    for(int i=0; i<n; i++){
        maxnum = max(check[n-1][i],maxnum);
    }
    
    answer = maxnum;
    return answer;
}