[Algo Rhythm🕺💃] 프로그래머스 고득점 kit 정수 삼각형

📚 문제 설명

 

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

 

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

 

🎯 어떻게 풀었나

1. DFS  (50/ 100) - 효율성 통과 🙅‍♀️🙅‍♂️🙅

	class Solution {
	    public int solution(int[][] triangle) {
	        return dfs(triangle, 0, 0, triangle[0][0]);
	    }
	    
	    public int dfs(int[][] arr, int lev, int idx, int sum) {
	        if(lev == arr.length - 1) return sum;
	        
	        return Math.max(dfs(arr, lev + 1, idx, sum + arr[lev + 1][idx]) //left
	                       ,dfs(arr, lev + 1, idx + 1, sum + arr[lev + 1][idx + 1])); // right
	    }
	}

 

2. DP - 모두 통과 😻😺😸

	class Solution {
	    public int solution(int[][] triangle) {
	        int answer = Integer.MIN_VALUE;
	        
	        int len = triangle.length;
	            
	        for(int i = 0; i < triangle.length; i++) {
	            if(i == 0) continue;
	            
	            int n = triangle[i].length;
	            
	            for(int j = 0; j < n; j++) {
	                int lParent = j - 1;
	                int rParent = j;
	                
	                if(j == 0) { //왼쪽 끝
	                    triangle[i][j] += triangle[i-1][rParent];
	                    continue;
	                }
	                
	                if(j == n - 1) { //오른쪽 끝
	                    triangle[i][j] += triangle[i-1][lParent];
	                    continue;
	                }
	                
	                triangle[i][j] += Math.max(triangle[i-1][lParent]
	                                          ,triangle[i-1][rParent]);
	            }
	        }
	        
	        for(int i = 0; i < triangle[len-1].length; i++) {
	            answer = Math.max(answer, triangle[len-1][i]);
	        }
	        
	        return answer;
	    }
	}

 

🧐 왜 저렇게 풀었나

1. DFS  (50/ 100) - 효율성 통과 🙅‍♀️🙅‍♂️🙅

DFS를 통한 접근은 간단하다. 삼각형 꼭대기부터 바닥까지 쭉 내려가고 바닥에 도달하면 계산된 값을 return 한다.

이때 현재 레벨에서 다음 레벨로 이동할 때는 왼쪽 혹은 오른쪽으로만 이동할 수 있다. 현재 레벨에 주목하고 있는 값의 index가 x라면 다음 레벨의 왼쪽의 index는 x, 오른쪽의 index는 x + 1이기 때문에 이를 통해 왼쪽 혹은 오른쪽 아래로 내려가는 것을 표현한다.

그리고 왼쪽으로 갈 때의 합와 오른쪽으로 갈 때의 합 중 더 큰 값을 return한다.

 

2. DP - 모두 통과 😻😺😸

DFS를 통한 방법은 정확하나 효율적이지 않다. 왜냐하면 필요없는 계산을 하기 때문이다.

그 이유는 다음과 같다.

아래와 같은 정수 삼각형이 있다고 가정하자. 빨간색 원이 그려진 1까지 도달하기 위해서는 두 개의 경로가 있다. 첫번째 경로는 7 -> 3 -> 1로 이어지고 합은 11이다. 두번째 경로는 7 -> 8 -> 1로 이어지고 합은 16이다. 여기서 우리는 1을 갈 때는 두번째 경로로 가는 것이 효율적이라는 것을 알 수 있다.

 

 

이를 위해 노드가 왼쪽 끝이나 오른쪽 끝이 아니라면 왼쪽으로부터 내려오는 경로와 오른쪽으로부터 내려오는 경로 중 합이 더 큰 경로로부터 내려온다고 하고 코드를 작성했다.

 

📖 무엇을 배웠나

필요없거나 중복되는 계산을 피하는 것이 DP의 본질이다!