[BOJ] 백준 1932 정수 삼각형

문제링크 : https://www.acmicpc.net/problem/1932

이 문제는 DP를 사용하여 삼각형의 꼭대기부터 최 하위층까지 어떤 경로를 택했을 때 경로를 이루는 원소의 합의 최댓값을 고르는 문제 입니다.

왜 DP일까요? 우리는 여러 경로를 따라가다 보면 중복되어 계산되는 위치의 원소가 있습니다. 이때 이 원소까지 오는 길을 최적화 하기 위해(계산을 덜 하기 위해) cache에 메모 해두는 것 입니다.

한 원소당 두가지 경우가 있으므로(좌, 우) 두 경우중 가장 큰 수를 캐싱합니다.

소스코드 :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <stack> #include <string> using namespace std; int n; vector<vector<int> > graph(501, vector<int>(501)); vector<vector<int> > cache(501, vector<int>(501, -1)); int DP(int a, int b) {     // 맨 아랫단에 도착한 경우     if (a == n) {         return graph[a][b];     }     // 이전의 발자취가 있을 경우     if (cache[a][b] != -1) {         return cache[a][b];     }          cache[a][b] = -1;     int na = a + 1;     int nb1 = b;     int nb2 = b + 1;     // 삼각형의 높이가 최대 높이를 오버하지 않는경우에만,      if (na <= n) {         // 왼쪽으로 가는게 1 이상인 경우에만, 혹은         if (nb1 >= 1) {             cache[a][b] = max (cache[a][b], graph[a][b] + DP(na, nb1));         }         // 오른쪽으로 가는게 그 높이에서 가질수있는 원소의 개수를 넘지 않는경우에만         if (nb2 <= na) {             cache[a][b] = max(cache[a][b], graph[a][b] + DP(na, nb2));         }         // 최댓값을 고른다.     }     return cache[a][b]; } Colored by Color Scripter

cs