1932번 정수 삼각형(DP) - ☆
#문제링크 : https://www.acmicpc.net/problem/1932
n : 삼각형의 크기
v : 각 정수를 담을 2차원 배열
big : 각 경로 합의 최대값
sum : 각 경로의 합
<1st try>
전략 : DFS로 왼쪽아래 가지를 먼저 탐색하고 이후 오른쪽 가지를 탐색해서 결과를 sum에 저장한 후 big과 비교하여 둘 중 큰 값을 big에 담는다. 백트래킹 할 시 해당 정수의 값을 sum에서 빼준다. 왼쪽가지 이후에 오른쪽 가지를 재귀로 들어가고 오른쪽가지가 끝나면 return해서 바로 윗 depth로 거슬로 올라가게 설계한다.
완탐이라, 시간복잡도가 O(N x 2^N)으로 말도안되게 많이 걸린다. 결과는 시간초과!
※주의사항
1. 배열인덱스는 N까지가 아니고 N-1까지 이므로, 유의한다.
<2nd try>
문제의 형태를 보면, 각 정수까지의 합이 여러번 중복 계산되는 것을 알 수 있다. 구하려는 값은 최댓값이므로, 한번 계산을 시작할때, 각 노드까지 합의 최대값으로 배열을 채우면 중복해서 계산할 필요 없이 바로바로 배열이 업데이트 된다.
단, 각 행의 첫번째와 마지막 노드는 부모 노드가 하나뿐이므로, 예외처리를 해주고, 나머지 노드는 모두 부모노드가 2개이기 때문에 둘중 큰값으로 선택후, 해당 노드와 더해서 해당 노드를 업데이트 한다.
출처 : https://jaemin8852.tistory.com/160
※주의사항
1. 가장 첫번째 행은 노드가 하나뿐이므로 시작을 두번째행부터 시작하고 더한다.
2. 최종적으로 마지막 행에 각 경로의 최대합이 저장되어 있으므로 마지막 노드들 중 최대값이 문제의 답이 된다.
