[프로그래머스, 43105] 정수 삼각형 (java)

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

728x90

---

메모리: 61.2 MB, 시간: 9.99 ms

사용 알고리즘: 동적계획법 (Dynamic Programming), DFS

 

dfs로 왼쪽 대각선으로 갔을 경우와 오른쪽 대각선으로 갔을 경우 중 더 큰 경우를 선택한다.

 

그런데 자신의 왼쪽에 있던 노드가 오른쪽 대각선으로 가는 경우와 자신이 왼쪽 대각선으로 가는 경우가 동일하니, 앞에서 이미 경우의 수를 구해놨다면 다시 구하지 않고 미리 저장해 둔 값을 사용한다.

import java.util.*;

class Solution {
    
    static int[][] triangle;
    static int[][] visited;
    
    public int solution(int[][] triangle) {
        
        this.triangle = triangle;
        
        // dfs를 이용하여 왼쪽 대각선으로 이동한 경우와 오른쪽 자식으로 이동한 경우 중
        // 더 큰 경우를 선택함
    
        // 이전 경우에서 이미 구한 경우는 다시 구하지 않음
        visited = new int[triangle.length][triangle.length];
        for(int i = 0; i < triangle.length; i++) Arrays.fill(visited[i], -1);
        
        // dfs
        int answer = dfs(0, 0);
        return answer;
    }
    
    private static int dfs(int height, int index) {
        
        int ret = triangle[height][index];
        
        // 리프 노드일 경우 자기 자신 리턴
        if(height == triangle.length - 1) {
            visited[height][index] = ret;
            return ret;
        }
        
        // 대각선 왼쪽으로 이동한 경우
        int leftChild;
        if(visited[height + 1][index] == -1) // 이전 노드에서 아직 안구한 곳만 다시 구하러 감
            leftChild = dfs(height + 1, index);
        else leftChild = visited[height + 1][index];
        
        // 대각선 오른쪽으로 이동한 경우(오른쪽 경우는 무조건 처음 구함)
        int rightChild = dfs(height + 1, index + 1);
        
        // 더 큰 경우를 더해줌
        ret += Math.max(leftChild, rightChild);
        
        visited[height][index] = ret;
        return ret;
    }
}