[프로그래머스] Lv.3 정수 삼각형 c++

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

프로그래머스

 

출처 : programmers

 

1층부터 n층까지 내려가는 경로중 숫자의 합이 가장 큰 경우를 찾으면 된다.

아래칸으로 이동시 대각선 왼쪽이나 대각선 오른쪽으로만 이동 가능하다.

ex) 7 -> 3 or 7 -> 8 

 

풀이 방법

레벨과 달리 생각보다 간단하다. dp로 풀면 된다.

맨 아래층 값들을 dp에 저장한 뒤 dp[0][0]이 될 때까지 올라간다.

예를 들어 위 이미지를 예시로 들면 현재 삼각형 크기가 5*5이므로 아래와 같이 dp[삼각형 세로길이][삼각형 가로 최대길이]에 저장한다.

dp[4][0] = 4

dp[4][1] = 5

dp[4][2] = 2

dp[4][3] = 6

dp[4][4] = 5

 

그 후 한칸 씩 위로 올라가면서 dp[3][0]에는 dp[4][0]과 dp[4][1]중 더 큰 값을,

dp[3][1]에는 dp[4][1]과 dp[4][1]중 더 큰 값을 더한다.

이런 식으로 dp[0][0]이 될 때까지 최댓값을 더해준다.

 

점화식은 아래와 같다.

 dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1]) 

 

풀이 코드

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

using namespace std;

int dp[500][500];
int solution(vector<vector<int>> triangle) {
    int answer = 0;

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