백준 4883 삼각 그래프

백준 4883 삼각 그래프

---

오늘은 삼각 그래프 문제를 풀었다.

DP 를 이용하면 풀 수 있겠다는 감이 바로 왔는데, 그래프를 내가 제대로 봤으면 쉽게 해결했을 것 같은데 그러지 않아서 오래 걸렸다. 또 신경 써야하는 문제점도 있었기 때문에 여러번 틀리고 나서야 답을 구할 수 있었다.

• 먼저, 그래프의 화살표가 어디로 향하는지 잘 봐야한다.
• 그 다음, 왼쪽 제일 위의 값을 신경을 써줘야 한다.

for (int i = 1; i<n; i++)
        {
            vector<int> v1;

            dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + table[i][0];
            dp[i][1] = min(dp[i-1][0], min(min(dp[i-1][1],dp[i-1][2]), dp[i][0])) + table[i][1];
            dp[i][2] = min(min(dp[i-1][1], dp[i-1][2]), dp[i][1]) + table[i][2];

        }

이렇게, 각 칸에 도달하는 화살표들은 전부다 Min 연산으로 값을 비교해 주어야 한다.


그리고,

dp[0][0] = 999999999;

이렇게 최대값으로 설정 안 해 두면 참조 하면 안되는데도 참조하기 때문에 문제가 발생한다!!!