[BAEKJOON] 4883 삼각그래프

?

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 48

#include <iostream> #include <vector> #include <algorithm> using namespace std;   int main() {     int n;     int t=1;     cin >> n;     while (n != 0)     {         vector<vector<int> > graph(n, vector<int>(3, 0));         vector<vector<long long> > d(n, vector<long long>(3, 0));           for (int i = 0; i < n; i++) {             for (int j = 0; j < 3; j++) {                 cin >> graph[i][j];             }         }         d[0][1] = graph[0][1];         d[0][2] = d[0][1] + graph[0][2];         for (int i = 1; i < n; i++) {             for (int j = 0; j < 3; j++) {                 if (j == 0) {                     d[i][j] = graph[i][j] + d[i - 1][j + 1];                     if (i != 1)                         d[i][j] = min(d[i][j], graph[i][j] + d[i - 1][j]);                 }                 else if (j == 1) {                     d[i][j] = graph[i][j] + d[i][j - 1];                     d[i][j] = min(d[i][j], graph[i][j] + d[i - 1][j]);                     d[i][j] = min(d[i][j], graph[i][j] + d[i - 1][j + 1]);                     if (i != 1)                         d[i][j] = min(d[i][j], graph[i][j] + d[i - 1][j - 1]);                 }                 else {                     d[i][j] = graph[i][j] + d[i][j - 1];                     d[i][j] = min(d[i][j], graph[i][j] + d[i - 1][j - 1]);                     d[i][j] = min(d[i][j], graph[i][j] + d[i - 1][j]);                 }             }         }           cout << t++ << ". " << d[n - 1][1] << endl;         cin >> n;     }     return 0; }

다른 사람의 코드이다 : https://www.acmicpc.net/board/view/17105

맨처음에는 다익스트라로 접근했다가

메모리 초과가 나서 어떻게 해야할지 생각했다.

이렇게 DP를 이용해서 풀수있는데..

그래서 분석했다.

일단 옆에서 오는 걸 확인한다

그리고 이전것과 더해서 최소값을 저장한다

이런문제 많이 풀어봤는데 도저히 생각이 안난다.

속상..