'다이나믹프로그래밍' 태그의 글 목록

정수 삼각형 풀이과정 삼각형의 가장 아래쪽에서부터 두 줄을 선택한다. 아랫줄을 currentLine, 그 윗 줄을 nextLine으로 설정. currentLine[i] 또는 currentLine[i + 1] 중에서 큰 값을 선택하여 nextLine[i] 에 더한다. nextLine 이 삼각형의 꼭대기를 가리킬 때 까지 currentLine, nextLine을 삼각형의 위로 올려가며 2번 과정을 반복한다. 삼각형의 꼭대기에 최댓값이 저장되므로 이를 반환한다. 위 과정과는 반대로 위에서부터 아래쪽으로 내려가면서 계산할 수도 있지만, 이렇게 풀이를 진행 할 경우 삼각형의 가장 아랫줄을 순회하면서 최댓값을 찾는 과정이 추가되므로 비효율적이다. Code class Solution { public int sol..