[4883번] 삼각 그래프

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

공간 복잡도를 줄이기 위해 DP를 굳이 배열로 두지 않고 변수로 선언하고,

아래 코드에 존재하는 점화식을 통해 해결한다.

첫행, 둘째행의 DP값은 점화식을 이용하는 for문에서 구하지 않고 직접 구해야 하며(시작점이 첫행 가운데 값이기에)

            prevA = dA;

            prevB = dB;

            dA = min(dA, dB) + a;

            dB = min(min(min(dA, dB), dC), prevA) + b;

            dC = min(min(dB, dC), prevB) + c;

이 점화식을 통해 해결할 수 있다.

(화살표를 잘 보고, 의미를 파악하면 점화식이 보인다. 

참고로 prevA는 dA가 변하기 전 즉, 이전 행의 값을 가져온 것이다.)

소스 코드 : 

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 49 50 51 52 53 54 55 56 57 58 59 60

#include <iostream> #include <cstdio> #include <algorithm>   using namespace std;   long long int a, b, c; long long int dA, dB, dC;   int main() {     int n, end;     long long int mid;     long long int prevA;     long long int prevB;     int tCase = 1;       // 정점의 비용이 양의 정수가 아닐 수 있다.     while(1)     {         scanf("%d", &n);           if (n == 0)             break;           scanf("%lld %lld %lld", &a, &b, &c);              // 첫행의 dp값은 고정된 값         mid = b;         dA = 0;         dB = b;         dC = b + c;              scanf("%lld %lld %lld", &a, &b, &c);              // 두번째 까지 dp는 dB가 모양이 다르므로 따로 계산해준다.         dA = dB + a;         dB = min(min(dA, dB), dC) + b;         dC = min(min(dB, dC), mid) + c;                  // 세번째 부터는 점화식에 맞게 대입         for (int i = 0; i < n - 2; i++)         {             scanf("%lld %lld %lld", &a, &b, &c);               prevA = dA;             prevB = dB;             dA = min(dA, dB) + a;             dB = min(min(min(dA, dB), dC), prevA) + b;             dC = min(min(dB, dC), prevB) + c;         }              printf("%d. %lld\n", tCase++, dB);         }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus