[c++][프로그래머스] 정수 삼각형

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

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

위에서부터 내려가면서 더한 값의 가장 큰 값을 구하는 문제입니다.

 

위에서부터 풀 수도 있는데 저는 아래에서 올라가는 방법으로 풀었습니다.

 

아래에서부터 좌우를 한개씩 비교해서 큰 값을 넣는 방법으로 올라가서 맨 위까지 올라가는 방법입니다.

 

예를 들어서,

 

a

b c

d e f 

 

가 있다면, b에는 b+d 와 b+e 를 비교해서 큰 값을 , c에는 c+e와 c+f를 비교해서 큰 값을 넣고 마지막에 a+b / a+c를 비교하는 방식입니다.

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int len = triangle.size();      // 삼각형의 높이
    
    for(int i=len-2; i>=0; i--)
    {
        for(int j=0; j<i+1; j++)
        {
            int left = triangle[i+1][j] + triangle[i][j];
            int right = triangle[i+1][j+1] + triangle[i][j];
            
            if(left > right)
            {
                triangle[i][j] = left;
            }
            else
            {
                triangle[i][j] = right;
            }
        }
    }
    
    answer = triangle[0][0];
    
    return answer;    
}