[알고리즘문제] 프로그래머스 - 정수 삼각형

전형적인 dp문제이다. 예전에 계산했던 결과를 사용하여 현재 계산하려는 값을 구할 수 있다.

만약 내가 dp를 배우지 않았다면 아마 완전탐색이나 dfs로 구현했을 것 같다. 

 

               7                     5층

            3   8                  4층

          8   1   0               3층

        2  7   4   4             2층

      4   5  2   6   5          1층

 

문제는 5층부터 1층까지 내려올 때 최대의 값이 얼마인지 구하는 문제이다. 제한 사항은 아래로 내려올 때 좌/우 1칸씩으로만 이동할 수 있다.

 

아이디어는 각 층(꼭대기층 제외)의 원소들에 현재 최선의 값을 저장하는 것이다. 여기서 "최선의 값"을 설명하면 n층의 k번째 원소에 도착할 수 있는 많~은 동선 중에서 그 값이 최대값이 경우이다.

 

예를 들어 3층의 1이라는 값에 도착할 수 있는 동선을 보자

 

7 - 3 - 1 = 11

7 - 8 - 1 = 16

 

여기서 2가지의 동선이 나오고, 1에 도착했을 때 최선의 값은 16이다. 이 값은 3층의 1값 대신에 넣어준다. 왜냐 ? 앞으로 2,1 층을 검사할 때 사용하기 위해서 이다.

 

위에서 설명한 아이디어가 dp이다. 처음에 와닿지 않을 수 있는데 사실 논리적이고 깔끔한 방법이다.

 

코드를 구현하기 앞서, 신경써야 할 부분은 좌/우 1칸씩으로만 이동할 수 있다고 했다. 예를 들어 3층의 0에서 2층의 2층의 2로 갈 수 없다고 하였다.

 

1. 2층의 7이라는 값을 계산할 때는 3층의 8과 1중에 값을 최대값을 선택해야 한다 : 최대값을 구하는 문제니깐

2. 각 층의 처음/마지막 원소는 값이 비교할 수 있는 값이 하나밖에 없다 : 끝에 있으니깐

 

위의 아이디어를 바탕으로 코드로 옮겨보자

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<vector<int>> triangle) {
    
    int answer = 0;
    
    for(int i=1;i<triangle.size();i++){                        // 꼭대기층은 원소가 하나이기 때문에 검사할 필요가 없다
       for(int k=0;k<triangle[i].size();k++){
           
           int upperLeft = triangle[i-1][k-1];
           int upperRight = triangle[i-1][k];
           
           int upperFirst = triangle[i-1][0];
           int upperLast = triangle[i-1][triangle[i-1].size()-1];
           
            if(k==0){                                          // n층의 맨앞에 있는 경우
                triangle[i][k]+=upperFirst;
            }else if(k==triangle[i][triangle[i].size()-1]){    // n층의 맨 끝에 있는 경우
                triangle[i][k]+=upperLast;
            }else{                                             // n층의 맨앞 ~ 맨끝 사이에 있는 경우, 그 위층의 좌/우 값 중 최대값을 선택
               triangle[i][k]+=max(upperLeft,upperRight);
            }
           
           answer = max(answer,triangle[i][k]);
       }
    }
    
    
    return answer;
}