[프로그래머스 정수삼각형] c++ (풀이, 코드, level3)

문제 링크

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

프로그래머스

문제

 

코드 및 풀이

누가 봐도 문제는 dp라고 생각합니다. level3라서 살짝 어렵지 않을까 했는데 프로그래머스의 level은 정말 무의미한게 아닐까 싶기도 합니다.. (level1에서도 하루종일 헤맸던 기억..)

 

이런 문제류들이 거꾸로 아래부터 위로 더하는 것이 편하다고 생각합니다.

 

하지만 저는 조금 다른 방법으로 접근해서

 

triangle[i]의 원소들을 접근할때 triangle[i-1]의 원소들에 앞뒤에 0을 넣어줘서 그것에 대한 

            if(triangle[i-1][j] > triangle[i-1][j+1])
                triangle[i][j] += triangle[i-1][j];
            else
                triangle[i][j] += triangle[i-1][j+1];

이렇게 맨앞과 맨뒤에 0은 무조건 갱신이 되지 않기 때문에 그것에 대해서 처리를 진행해주었습니다 :)

 

\

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int solution(vector<vector<int>> triangle) {

    int answer = 0;

   

    for(int i = 1; i < triangle.size();i++){

        //케이스를 맨 왼쪽, 맨 오른쪽, 가운데 기준으로 생각하면 되지 않을까?

        //이거를 그냥 맘 편하게 양쪽에 0을 넣어버리면 편할듯?

        // 0 7 0 -> 3 8이니깐  또 0 10 15 0 -> 8 1 0 비교 편함!

        triangle[i-1].insert(triangle[i-1].begin(),0);

        triangle[i-1].push_back(0);

        for(int j  = 0; j < triangle[i].size();j++){

            if(triangle[i-1][j] > triangle[i-1][j+1])

                triangle[i][j] += triangle[i-1][j];

            else

                triangle[i][j] += triangle[i-1][j+1];

        }

    }

   

    // 맨 마지막 바닥 원소에 대해서 크기 측정

    answer = *max_element(triangle[triangle.size()-1].begin(),triangle[triangle.size() -1].end());

   

   

    return answer;

}