코딩 테스트
(Java) 프로그래머스 - 정수 삼각형
문제 유형에 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[][] ..
