[백준][DP] 1932 : 정수 삼각형

문제

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

필요 지식

 - dynamic programming

해결 방법

 - 2개의 삼각형이 필요 : cost, sub

     - cost : 입력 값 (그 삼각형 고유의 cost)

     - sub : 현재 위치까지 최대 합 값

 - cost, sub 삼각형 배열로 옮기면.. (밑 형태 sub도 동일)

        cost(0,0)

        cost(1,0) cost(1,1)

        cost(2,0) cost(2,1) cost(2,2)

  - sub는 어떻게 나타낼 수 있는가?

        sub(0,0) = cost(0,0)

        sub(2,0) = sub(1,0) + cost(1,0)

        sub(2,1) = max(sub(1,0), sub(1,1)) + cost(2,1)

        sub(2,2) = sub(1,1) + cost(2,2)

  

        -> 요약 ) sub(i,j) 대해서...

                j = 0이거나 j=i 이 아닌 경우,

                sub(i,j) = max(sub(i-1,j-1), sub(i-1,j)) + cost(i,j)

주의할 점

 - 메모리 생각

• 특히 DP같은 문제에서 더해가다가 숫자가 굉장히 커질 수 있으므로,
• int같은 작은 범위 가지는 변수말고, long long등을 지정해야함

코드

반성할 점

 - cost와 sub를 굳이 나눌 필요는 없었음. 공간만 2배 차지하게 된 셈