[백준/Baekjoon] 1932 정수 삼각형 C++ :: Dynamic Programming

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

---

1. Logic

- Topdown 방식으로 풀이

현재 index에서 갈 수 있는 방향이 한정되어있기 때문에 아래의 좌우 로 한개씩 보내주고 리턴되는 값 중 최댓값을 대입한다.

 

DP table : dp[몇번째 층인지][몇번째 숫자인지]

 

재귀를 타고 내려가면서 층수를 한개 올려주고 현재 노드의 인덱스와 같은 인덱스 한개 + 1한 인덱스 한개를 재귀로 보내줫다.

 

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;

int dp[501][501];

vector<int> vec[501];

int solve(int floor, int idx) {
    if(floor == n) return 0;
    int &ret = dp[floor][idx];
    if(ret != -1) return ret;

    ret = 0;

    ret = max(ret, solve(floor + 1, idx) + vec[floor][idx]);
    ret = max(ret, solve(floor + 1, idx + 1) + vec[floor][idx]);
    
    return ret;
}

int main() {
    memset(dp, -1, sizeof(dp));
    cin >> n;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            int a;
            cin >> a;
            vec[i].push_back(a);
        }
    }

    cout << solve(0, 0);
}

 

 

---

 

 

3. Feedback

- 드디어 DP를 답 안보고 혼자 완벽하게 풀어서 뿌듯하다~!