[프로그래머스/Level 3] 정수 삼각형 (C++)

programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

DP유형의 문제로, 백준의 1932번과 똑같은 문제였습니다. DFS를 호출할 때, 2차원 입력값을 전역변수로 설정하지 않고 매번 호출하게 되면 메모리 낭비로 인한 시간초과가 발생할 수 있기 때문에 전역으로 따로 선언 후, 값을 복사해주었습니다.

 

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

int dp[501][501];
vector<vector<int>> cpy;

int DFS(int x, int y, int size) {
    if(dp[x][y] != -1) return dp[x][y];
    if(x == size - 1) return cpy[x][y];
    
    return dp[x][y] = max(DFS(x + 1, y, size), DFS(x + 1, y + 1, size)) + cpy[x][y];
}

int solution(vector<vector<int>> triangle) {
    memset(dp, -1, sizeof(dp));
    cpy = triangle;
    
    return DFS(0, 0, triangle.size());
}

 

 

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

int dp[501][501];

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