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

코딩테스트 연습 - 정수 삼각형 문제 바로가기

문제 설명

삼각형의 위쪽 꼭지점에서 아래쪽으로 이동하면서 각 숫자를 합해 가장 큰 숫자를 만드는 문제입니다.
이 문제는 그림을 그렸을 때, 이진 그래프처럼 보이는 문제이지만
그래프를 만들 필요도 없이 메모이제이션 기법으로 간단하게 풀 수 있습니다.

시간 복잡도 실패

처음 문제를 접근할 때, 재귀 함수와 메모이제이션 기법으로 문제를 풀고자 하였습니다.
그러나 효율성 테스트에서 시간 초과로 인한 오답 판정이 나왔었습니다.

#include <string>
#include <vector>

using namespace std;

int DEPTH;
vector<vector<int>> ground;
vector<vector<int>> memo;

int dig_ground(int curr_depth, int curr_wid) {
    if(curr_depth < curr_wid) {
        return 0;
    }
    else if(curr_depth == DEPTH - 1) {
        return ground[curr_depth][curr_wid];
    } 
    else if(memo[curr_depth][curr_wid] != 0) {
        return memo[curr_depth][curr_wid];
    }
    
    return memo[curr_depth][curr_wid]
     = ground[curr_depth][curr_wid]
        + max(dig_ground(curr_depth + 1, curr_wid), 
              dig_ground(curr_depth + 1, curr_wid + 1));
}

int solution(vector<vector<int>> triangle) {
    DEPTH = triangle.size();
    ground = triangle;
    memo.assign(501, vector<int>(501, 0));
    return dig_ground(0, 0);
}

[효율성 테스트에서 실패한 결과]

문제 해결 코드

재귀 함수로 호출 스택이 커져 시간 초과가 발생했다고 생각했습니다.
따라서 이 문제점을 해결하기 위해서 재귀 함수 방법 대신 반복문 을 사용해서 풀고자 하였습니다.
이때, 메모이제이션 기법과 함께 사용해 연산 속도를 높이고자 하였습니다.

#include <string>
#include <vector>

using namespace std;

int memo[501][501];

int solution(vector<vector<int>> triangle) {
    int DEPTH = triangle.size();
    int answer = 0;
    memo[0][0] = triangle[0][0];
    
    for(int depth = 1; depth < DEPTH; ++depth) {
        for(int wid = 0; wid < triangle[depth].size(); ++wid) {
            if(wid == 0) {
                memo[depth][wid]
                    = triangle[depth][wid] + memo[depth - 1][0];
            }
            else if(wid == triangle[depth].size() - 1) {
                memo[depth][wid]
                    = triangle[depth][wid] + memo[depth - 1][wid - 1];
            }
            else {
                memo[depth][wid]
                    = triangle[depth][wid] + max(memo[depth - 1][wid], 
                                                 memo[depth - 1][wid - 1]);
            }
        }
    }
    
    for(int n : memo[DEPTH - 1]) {
        answer = max(answer, n);
    }
    return answer;
}