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

출처: 프로그래머스 코딩테스트 연습 ,https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

[문제풀이]
정수삼각형에 대한 데이터가 2차원 배열으로 주어진다.

우리가 기억해야 할 값들은

정수삼각형을 타고 아래로 내려가면서

이 칸까지 오면서 숫자를 더했을때에 가능한 최댓값, 단 하나 뿐이다 .

즉 2번째 줄에선 10과 15만 기억하면 되는것이고, 

3번째 줄의 8에서는 10에 8을 더한 18만,

3번째줄의 1에서는 10과 15중에 큰 15를 1에 더한 16만, 

 

3번째 줄의 0에서는 15를 더한 15만 기억하면 된다.

즉 n번째 줄에서는, 맨 처음과 끝 값은 바로 위의 값을 더한 값을, 그리고 중간에 있는 1번째값부터 n-1 번째 값 까지는 

위의 두가지 값중에 큰 것만 더해서 기억시키면 된다.

그러면 맨 밑에 n 번째 줄에 가장 큰 값들을 가진 경우의수 n개가 나오게 되는데,

이중에서 가장 큰 것을 탐색하면 된다.


[코드]

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int N = triangle.size();
    for(int i = 1 ; i < N ; i++){
        for (int j = 0 ; j < triangle[i].size() ;j++){
            if (j == 0){
                triangle[i][j] += triangle[i-1][j];
            } 
            else if (j == triangle[i].size() - 1){
                triangle[i][j] += triangle[i-1][j-1];
            }
            else{
                triangle[i][j] += max(triangle[i-1][j],triangle[i-1][j-1]);
            }
        }
    }
    
    for (int i = 0 ; i < N ; i++){
        answer = max(answer,triangle[N-1][i]);
    }
    return answer;
}