[BAEKJOON] 4883 삼각그래프

#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를 이용해서 풀수있는데..

그래서 분석했다.

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

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

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

속상..