프로그래머스, 정수 삼각형 : C++ [CPP]

사실 1로만 테두리가 이루어져있으면

파스칼 삼각형이었던가

이항정리할 때 배운듯한 느낌이 있다

 

 

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

 

---

 

#맞은 풀이

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

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    int row = triangle.size(); // 삼각형 높이 = 행 숫자;
    
    //삼각형 높이가 1이면 작동안함(2번째행부터 항상시작)
    for(int i = 1; i<row; i++){
        int length = triangle[i].size(); // 해당 행의 size
        
        //첫번째
        triangle[i][0] += triangle[i-1][0];
        //중간 -> 해당 행의 원소가 3개 이상일 때만 작동
        for(int j=1; j<length - 1; j++){
            int temp = max(triangle[i-1][j], triangle[i-1][j-1]);
            triangle[i][j] += temp;
        }
        //마지막
        triangle[i][length-1] += triangle[i-1][length-2];
    }
    
    //마지막 행의 array 를 vector로 변환시킴
    vector<int> vec(begin(triangle[row-1]), end(triangle[row-1]));
    
    //마지막 행에서 가장 큰 값 반환
    answer = *max_element(vec.begin(), vec.end());
    return answer;
}

 

10분만에 풀어서 너무 기분이 좋다.

내가 생각한대로 풀린다는게 엄청 기분이 좋다.

 

사실 정삼각형이지만

왼쪽을 등진 직각삼각형이라고 풀어야 저런 풀이가 가능하다.