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

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

풀이

문제를 읽은 후 DP로 풀어야겠다고 생각을 하고, 삼각형의 꼭대기부터 바닥까지 각 층에서 어떻게 윗 층의 정보를 가져와야 할지? 를 생각했다.

각 층에서 시작과 마지막 부분은 윗 층에서 가져온 숫자를 그냥 더해주고, 가운데 부분은 두개의 값을 비교하여 그중에 큰 숫자를 더하도록 해주었다.
그리고 마지막 바닥층에서 가장 큰 값을 반환하도록 코드를 작성했다.

+) 바닥층에서 부터 꼭대기까지 올라가는 방법으로 푸신 다른 분들의 풀이를 봤다.
이 방법으로도 한번 풀어봐야겠다.

코드

내가 작성한 코드

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

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

새롭게 배운 코드

#include <vector>
using namespace std;

int solution(vector<vector<int>> triangle) {
    int height = triangle.size();
    for(int i = height-2 ; i >= 0 ; i--){
        int cur_height = triangle[i].size();
        for(int j = 0 ; j < cur_height ; j++){
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]);
        }
    }
    return triangle[0][0];
}