문제 유형에 DP라고 쓰여있었기 때문에 어떻게 DP로 구현해야 할지 고민을 많이 했다. 점화식을 떠올리기 쉽기 때문에 레벨 3보다는 레벨 2에 더 적합한 문제라는 생각이 들었다. Bottom-up 방식이 가장 먼저 떠올라서 풀었지만 Top-down 방식으로도 풀이가 가능할 것 같다. 로직 가장 밑에 층에서부터 가장 위층까지 올라가며 각 층의 최댓값을 찾는다. 그 층에서 최댓값을 찾았다면 바로 위층에 i - 1에 해당하는 값을 더해서 바꿔준다. 결과적으로 가장 위층에는 최댓값이 남게 된다. 점화식은 triangle[i - 1][j] = triangle[i - 1][j] + triangle[i][j] 의 최댓값이다. 최종 코드 class Solution { public int solution(int[][] ..

문제의 그림부터 DP 문제라고 알려주고 있었다. 꽤나 많은 문제들을 풀면서 이제 문제를 보면 어떤 유형인지 대충 어떻게 설계를 해야 하는지는 알 수 있다. 다만 실제로 구현하는것은 아직도 조금 힘들다. 입력값을 배열로 만들고 마지막 배열의 값을 dp 배열에 복사하는 것이 첫 번째이다. 그리고 정점의 노드부터 재귀를 통해 내려온다. 마지막 노드에 도착하면 왼쪽과 오른쪽의 값 중 큰 값을 선택하고 배열의 값과 더해 dp의 값이 된다. 이런 식으로 모든 노드를 순회하면 dp[0][0] 값이 최댓값이 되어 출력하면 된다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; pu..