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

문제

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

사용 알고리즘

- 동적계획법(Dynamic Programming)

해결방법

• 2차원 db배열을 만들어 구한다.
  • dp[i][j] == (i, j) 지점까지 가는데 발생한 최대 경비
• 꼭대기에서 바닥까지 이어지는 경로를 구하는데, 이 때 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능
  • dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
  • dp[2][1] = max(dp[1][0], dp[1][1]) + triangle[2][1]
• 각 층의 첫 번째 자리는 위 층에서만 갈 수 있다
  • dp[i][0] = dp[i-1][0] + triangle[i][0]
  • dp[3][0] = dp[2][0] + triangle[3][0]
• 각 층의 마지막 자리는 위 층의 왼쪽 자리에서만 갈 수 있다.
  • dp[i][i] = dp[i-1][i-1] + triangle[i][i]
  • dp[4][4] = dp[3][3] + triangle[4][4]

테스트케이스 1번

 

i   \   j	[0]	[1]	[2]	[3]	[4]
[0]	7
[1]	3	8
[2]	8	1	0
[3]	2	7	4	4
[4]	4	5	2	6	5

 

• dp[바닥][0~삼각형크기] ==> for 문으로 돌면서 가장 큰 값을 구한다

 

소스코드

사용언어 : C++

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

int dp[501][501];

int solution(vector<vector<int>> triangle) {   
    dp[0][0] = triangle[0][0];
    
    for(int i = 1; i < triangle.size(); i++) {
        dp[i][0] = dp[i-1][0] + triangle[i][0]; //각 층의 첫 번째 자리
        dp[i][i] = dp[i-1][i-1] + triangle[i][i]; //각 층의 마지막 자리
        for(int j = 1; j < i; j++){
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
        }
    }
    
    int last_floor = triangle.size() - 1;
    int max_path_num = dp[last_floor][0];
    for(int i = 1; i < last_floor; i++) {
        if (dp[last_floor][i] > max_path_num) {
            max_path_num = dp[last_floor][i];
        }
    }
    
    return max_path_num;
}

 

한줄평

전형적인 dp 문제. . 

사용가능 언어에 javascript가 없어서 c++로 풀었다.

2차원 vector 길이 구할 때는 .size() 잊지말자.