프로그래머스 - 정수 삼각형(Level 3)

처음엔 dfs로 풀려했지만 시간초과가 떴다

찾아보니 dfs로 풀 수 있는 연산은 대충 500만 개 정도이다.

그러나 이 문제는 삼격형의 높이가 500이하이므로 2^500-1번의 조합을 찾아야 한다.

500만 개 훨씬 넘으므로 시간초과가 뜨는 게 당연하다.

 

 

< 동적프로그래밍 >
큰 문제를 작은 문제로 분할하여 해결하는 알고리즘이다.
작은 문제를 풀때마다 항상 값이 같다.
-> 고로 작은 문제의 답을 어딘가에 메모해놓는다. 

→ Memoization
-> 메모리에 저장해서 중복 연산을 줄인다

 

dp로 푼 풀이

1. 합을 메모해둘 triangle과 같은 크기의 자료구조 생성

2. 왼쪽 끝과 오른쪽 끝 그리고 나머지 이렇게 구분해서 

규칙을 찾아 더한다.

3. 최대값을 저장한다.

 

class Solution {

    public int solution(int[][] triangle) {
        int answer=0;
        int[][] tree=new int[triangle.length][];
        for (int i = 0; i < triangle.length; i++) {
            tree[i] = new int[triangle[i].length]; //꼭 크기 지정해줘야함. 안그럼 에러뜸
}
        //triangle과 같은 자료구조 생성, 이곳에 값을 저장
        tree[0][0]=triangle[0][0];
        
        for(int i=1;i<triangle.length;i++){
            for(int j=0;j<triangle[i].length;j++){
                if(j==0) //왼쪽 끝
                    tree[i][j]=tree[i-1][j]+triangle[i][j];
                else if(j==i) //오른쪽 끝
                    tree[i][j]=tree[i-1][j-1]+triangle[i][j];
                else
                    tree[i][j]=triangle[i][j]
                    +Math.max(tree[i-1][j],tree[i-1][j-1]);
                
                answer=Math.max(answer,tree[i][j]);
                
            }
        }
      return answer;
    }
}

 

 

---

memozation을 사용한 dfs 방법

 

: 아래에서 위로 올라오며 최댓값을 더해나가는 과정

class Solution {

    public int solution(int[][] triangle) {
        int[][] memo = new int[triangle.length][triangle.length];
        return dfs(triangle, 0, 0,memo);
    }

    public int dfs(int[][] triangle, int i, int j,int[][] memo) {
        // 이미 계산된 경우 메모이제이션된 값을 반환
        if (memo[i][j] != 0) {
            return memo[i][j];
        }

        // 마지막 행에 도달한 경우 현재 위치의 값을 반환
        if (i == triangle.length - 1) {
            return memo[i][j] = triangle[i][j];
        }

        // 계산이 안 된 경우 아래쪽 혹은 대각선 오른쪽으로 이동하며 최대값을 찾음
        return memo[i][j] = triangle[i][j] + 
            Math.max(
            dfs(triangle, i + 1, j, memo), dfs(triangle, i + 1, j + 1, memo));
    }
}