프로그래머스 (Level 3) : 정수 삼각형/ C++, DP/ vector 최대값 *max_element, greater<>()

문제

프로그래머스

 

 

출처 : 프로그래머스

 

위와 같은 삼각형의 꼭대기에서 바닥까지 아래 칸으로 이동할 때 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능

(예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능)

삼각형의 정보가 담긴 배열 triangle이 주어질 때, 거쳐간 숫자의 최댓값을 return

 

 

 

 

풀이

 

노드 높이가 1일 때부터 부모노드 중 가능한 값을 더하며 그 중 최대값을 저장하도록 구현했다.

 

발그림;; 각 삼각형의 값들과 인덱스

 

위의 그림처러 세 가지 경우로 나누어 계산했다.

인덱스가 (x,y)라고 했을 때,

 

1)  y=0 인경우 > 접근 가능한 부모1  (x-1,0)

2) y=해당 배열의 최대 인덱스인 경우 > 접근 가능한 부모1 (x-1, size)

3) 그 외 > 접근 가능한 부모2 (x-1, y-1), (x-1,y)

 

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

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    vector<vector<int>> ct=triangle;
    
    for(int i=1;i<ct.size();i++){
        for(int j=0;j<ct[i].size();j++){
            if(j==0)ct[i][j]+=ct[i-1][0];
            
            else if(j==ct[i].size()-1)ct[i][j]+=ct[i-1][ct[i].size()-2];
            
            else ct[i][j]+=(max(ct[i-1][j-1],ct[i-1][j]));
        }
    }
    //greater<>() 내림차순, *max_element = algorithm include
    sort(ct[ct.size()-1].begin(),ct[ct.size()-1].end(), greater<>()); 
    answer = ct[ct.size()-1][0];
    //answer = *max_element(ct[ct.size()-1].begin(), ct[ct.size()-1].end());
    return answer;
}

 

완탐으로 누적합들을 계산한 뒤 

마지막 배열에서의 최대값을 구해 return 했다.

 

 

---

 

 

*최대값 구하는 방식*

algorithm 헤더 필요!

 

1) 내림차 순 정렬 후 마지막 배열의 0번째 값 return : greater<>()

2) *max_element(v.begin(), v.end())