프로그래머스 정수 삼각형 c++

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

인자가

1

22

333

4444

55555

이런식으로 vector<vector<int>> 형식으로 들어오므로

재귀함수로 모든 경우를 다 탐색하려 했다.

#include <string> <실패코드>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

vector<vector<int>> tri;
vector<int>         v(501);

void    recur(int i, int j, int sum) {
    sum += tri[i][j];
    if (i == tri.size() - 1) // 맨 아랫줄일때
        v[j] = max(v[j], sum);
    else {
        recur (i + 1, j, sum);
        recur (i + 1, j + 1, sum);
    }
}

int solution(vector<vector<int>> triangle) {
    tri = triangle;
    recur(0, 0, 0);
    return (*max_element(v.begin(), v.end()));
}

정확성 테스트

테스트 1 〉	통과 (0.01ms, 4.21MB)
테스트 2 〉	통과 (0.01ms, 3.67MB)
테스트 3 〉	통과 (0.08ms, 3.66MB)
테스트 4 〉	통과 (2496.82ms, 4.2MB)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	통과 (0.01ms, 4.2MB)
테스트 10 〉	통과 (1645.84ms, 4.2MB)

효율성 테스트

테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)

네 안됩니다.

시간초과 이렇게 뜨는 거면 dp입니다.

#include <string>
#include <string.h> // memset땜시
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
//1
//22
//333
//4444  [3][3]
//55555 [4][3]. [4][4]

int solution(vector<vector<int>> triangle) {
    int size = triangle.size();
    int dp[size][size];
    
    memset (dp, 0, sizeof(dp));
    for (int i = 0; i < size; i++) // 맨 아래줄만 초기화
        dp[size - 1][i] = triangle[size - 1][i];
    for (int h = size - 2; h >= 0; h--) // 맨아래의 두번째 줄부터 더하면서 dp테이블 만든다.
        for (int w = 0; w < size - 2; w++) // 현재 위치의 아래 두개중 큰거를 더해줌
            dp[h][w] = triangle[h][w] + max(dp[h + 1][w], dp[h + 1][w + 1]);
    return (dp[0][0]);
}

ez