프로그래머스 - 정수 삼각형 - Level 3

문제

풀이전략

1. 메모이제이션을 하여 중복된 경로를 지나지 않도록 해결한다.
2. Queue를 이용하여 순차적으로 밑으로 진행한다.

코드

#include <string>
#include <vector>
#include <queue>
using namespace std;
struct tri{
    int i, j, val;
    // 삼각형의 위치와 그 위치에서의 값을 저장한 구조체
    tri(int a, int b, int c){
        i = a;
        j = b;
        val = c;
    }
};
int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    int ch[501][501];
    queue<tri> q;
    // 시작점을 먼저 넣어준다. 
    q.push(tri(0,0,triangle[0][0]));
    ch[0][0] = triangle[0][0];
    while(!q.empty()){
        tri ret = q.front();
        int i = ret.i;
        int j = ret.j;
        int val = ret.val;
        
        q.pop();
        // ch에 저장된 최대값일 때만 queue를 진행한다. 
        if(ch[i][j] > val) continue;
        if(i == triangle.size()-1) continue;
        
        // 바로 밑으로 갈때 값비교를 해주어 더 크다면 그 값을 저장해주고 q에 넣어준다. 
        if(ch[i+1][j] < val + triangle[i+1][j]){
            ch[i+1][j] = val + triangle[i+1][j];
            q.push(tri(i+1, j, val + triangle[i+1][j]));
        }
        // 대각밑으로 내려갈때 값비교를 해주어 내려간다. 
        if(ch[i+1][j+1] < val + triangle[i+1][j+1]){
            ch[i+1][j+1] = val + triangle[i+1][j+1];
            q.push(tri(i+1, j+1, val + triangle[i+1][j+1]));
        }
        
    }
    int lastIndex = triangle.size()-1;
    for(int k=0; k<triangle[lastIndex].size(); k++){
        if(answer < ch[lastIndex][k]) answer = ch[lastIndex][k];
    }
    return answer;
}

소감

간만에 DP문제를 풀어서 조금 헤맸지만.... 이러한 테크닉들을 잊지말아야한다. 점화식도 세울 수 있다는 것을 잊지말자.!