Best Path On a Diamond

문제 : http://algospot.com/problems/read/DIAMONDPATH


접근 방법
Solution을 도출하기까지의 과정은 굉장히 빨랐다.
다만, 쌍for 한번으로 다이아몬드를 받아내려고, 테크닉을 부리다가 시간이 꽤 지났다..
(그냥 쌍for로 상단 삼각형모양받고 , 다시한번 쌍for로 받아도 되는걸 객기 부려봤다.;)

Input은 다소 낭비가 있더라고 다이아몬드를 받을 수 있는 크기의 2차원 배열(Notj jagged)로 받아서 처리했다. Memoization을 위한 배열 역시 같은 크기의 Array를 사용하였다.
다이아몬드 임의의 위치 n자신의 Cost를 Cost(n)이라고 하고, n까지의 도달하는데 최대Cost를 An이라고 하자.
An = Cost(n) + MAX( n에 도달할 수 있는 2개까지의 Path (A(n-1))
Array로 표현하자면,
Path[n][k] = Cost[n][k] + Max(Path[n-1][k],Path[n-1][k-1])  // 다이아몬드 확장 루틴
Path[n][k] = Cost[n][k] + Max(Path[n-1][k],Path[n-1][k+1])  // 다이아몬드 축소 루틴
// n-1, k-1, k+1을 하기 때문에 Index Overflow, Underflow관리는 알아서 해줘야 하는 사안.

// Maximum Cost로 Table Construction
  bool flag=false;
  tmpsize = size;
  path[0][0] = dia[0][0];
  for(int i=1; i<2*size-1; i++)
  {
   if( i>=size ) {tmpsize--; flag=true;}
   for(int j=0; j<tmpsize; j++)
   {
    if(flag) path[i][j] = dia[i][j] + max(path[i-1][j+1], path[i-1][j]);
    if( j==0 && !flag ) path[i][j] = dia[i][j]+path[i-1][j];
    else if(!flag)path[i][j] = dia[i][j] + max(path[i-1][j-1], path[i-1][j]);
    if( i==j ) break;
   }
  }

몇문제 풀고 보니 DP가 분석 후 문제 구축만 잘해내면 프로그래밍은 굉장히 깔끔하고
코드도 짧다.