알고리즘(C++) / 프로그래머스 level 3 : 정수 삼각형

level 3 : 정수 삼각형

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

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

 

코드

//프로그래머스 정수 삼각형
#include <iostream>
#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++) { //두번째 줄부터
        for (int j = 0; j < triangle[i].size(); j++) {
            if (j - 1 < 0)
                triangle[i][j] += triangle[i - 1][j]; //오른쪽 위
            else if (j == i)
                triangle[i][j] += triangle[i - 1][j - 1]; //왼쪽 위
            else
                triangle[i][j] += max(triangle[i - 1][j - 1], triangle[i - 1][j]); //오른쪽 위, 왼쪽 위 중 더 큰 값

        }
    }
    
    answer = *max_element(triangle[triangle.size() - 1].begin(), triangle[triangle.size() - 1].end()); //바닥에서 가장 큰 수

    return answer;
}

int main() {
    vector<vector<int>> triangle = { {7}, {3,8}, {8,1,0}, {2,7,4,4}, {4,5,2,6,5} };
    cout << solution(triangle) << "\n";
    return 0;
}

 

설명

 

• 꼭대기에서부터 역삼각형을 그려 왼쪽 위와 오른쪽 위 수 중 큰 수를 선택하여 밑에 숫자와 합해준다.
• 왼쪽 위와 오른쪽 위 중 하나가 존재하지 않다면 그대로 밑에 숫자와 합해준다.
• 바닥까지 구한 후 바닥 벡터에서 가장 큰 수를 출력한다.

 

고찰

걸린시간 : 20분

DP 문제임에도 불구하고 쉽게 풀 수 있었다. 재귀 함수(top-down)를 사용하지 않고 반복문(bottom-up)을 사용하여 DP문제를 구현할 수 있었다. 

벡터에서 최댓값을 구하기 위해 *max_element를 사용한다. 하지만 max와 헷갈려서 찾아보았다. 벡터에서 최댓값을 구하기 위해 *max_element을 기억하자.