문제정수 삼각형문제 해설문제에는 꼭대기에서 바닥으로 이어지는 경로라고 주어졌지만 이 문제는 상향식(Bottom - up) 방법을 이용하면 쉽게 풀 수 있다.각 노드의 좌측 아래 노드의 값과 우측 아래 노드의 값을 비교하여 더 큰 값과 현재 노드의 값을 더한 값을 현재 노드 위치에 저장한다. 이 과정을 루트 노드까지 반복하여 루트 노드까지 가는 경로 중 숫자의 합이 최대 값을 찾을 수 있다.class Solution { public int solution(int[][] triangle) { int[][] memo = new int[triangle.length][]; for (int i = 0; i = 0; i--) { for (int j = 0; j

문제등굣길문제 해설각 노드에 지나가는 경로의 수를 저장하고 학교 노드의 왼쪽 노드와 위 노드의 숫자를 더한 값을 반환하는 방법은 모든 경로가 저장된다. 때문에 아래 그림처럼 최단 경로가 아닌 경로도 포함되는 문제가 있다.하지만 문제를 보면 오른쪽과 아래쪽으로만 움직일 수 있다는 조건이 있다. 이는 모든 경로가 최단 경로임을 의미하므로 아래와 같이 각 노드에 지나가는 경로의 수를 저장한 뒤 학교 노드의 왼쪽 노드와 오른쪽 노드의 수를 더한 값을 저장하는 방식으로 풀 수 있다.class Solution { public int solution(int m, int n, int[][] puddles) { int[][] map = new int[n][m]; map[0][0] = 1; ..