[프로그래머스] 3단계 - 정수 삼각형

문제 설명

삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합 중 최댓값을 return 

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

프로그래머스

 

문제 풀이법

아무래도 삼각형은 dp의 대표적인 문제 같다

 

우선 dp문제이므로 배열을 하나 선언해주고, 삼각형의 맨 꼭대기 숫자를 넣어준다

 

이후 for문을 돌면서 값을 넣어주는데 맨 왼쪽이나, 맨 오른쪽 값이면 위의 숫자를 바로 넣어준다

만일 y좌표가 i고 x좌표가 j일때 맨 왼쪽 값이면, dp[i - 1][0] 값과 현재 삼각형의 숫자를 더한 값을 배열에 넣어준다

맨 오른쪽 값이면, dp[i - 1][j - 1] 값과 현재 삼각형의 숫자를 더한 값을 배열에 넣어준다

맨 오른쪽 값과 왼쪽 값이 아니라면 비교를 해주면서 큰 값을 더해줘야하는데, dp[i - 1][j - 1]와 dp[i - 1][j] 값 중에 큰 값과 현재 삼각형의 숫자를 더한 값을 배열에 넣어준다

 

값을 다 넣어줬으면, 삼각형의 맨 밑의 값들을 한번씩 보면서 최댓값을 return 해준다

 

 

소스 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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