[프로그래머스, 자바] 정수 삼각형 - 동적계획법

프로그래머스 3단계 정수삼각형 문제

 url : https://programmers.co.kr/learn/courses/30/lessons/43105?language=java

문제설명

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

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

제한사항

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

입출력 예

triangle	return
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	[2,1,1,0]

입출력 예 설명

1초 시점의 ₩498은 2초간 가격을 유지하고, 3초 시점에 ₩470으로 떨어졌습니다.

2초 시점의 ₩501은 1초간 가격을 유지하고, 3초 시점에 ₩470으로 떨어졌습니다.

3초 시점의 ₩470은 최종 시점까지 총 1초간 가격이 떨어지지 않았습니다.

4초 시점의 ₩489은 최종 시점까지 총 0초간 가격이 떨어지지 않았습니다.

자바코드

 (1) 브루트 포스 - 완점탐색 : 일부 테스트 케이스 시간초과, 실패

            
public int solution(int[][] triangle) {
        return dp(0, 0, triangle);
    }
   
   public int dp(int depth, int index, int[][] triangle) {
      if(depth >= triangle.length) 
         return 0;   
      
      return triangle[depth][index] + Math.max(dp(depth + 1, index, triangle), dp(depth + 1, index + 1, triangle));
   }

 (2) 동적계획법 : 성공

            
   public int solution(int[][] triangle) {
        // 1. 기본값 초기화  //
      int[][] dp = new int[triangle.length][triangle.length];
        dp[0][0] = triangle[0][0];
        for(int i = 1; i < triangle.length; i++) {
           dp[i][0] = dp[i - 1][0] + triangle[i][0]; 
           dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
        }
        
        // 2. 동적계획법 //
        for(int i = 2; i < triangle.length; i++) 
           for(int j = 1; j < i; j++) 
              dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
        
        // 3. 최대값 반환 //
        int max = 0;
        for(int i = 0; i < dp.length; i++) 
           max = Math.max(max, dp[dp.length - 1][i]);
      
      return max;
    }

문제설명

처음 문제를 풀었을 때는 브루트포 - 완점탐색을 이용해서 풀었다. 아래 그림을 이용해서 설명을 해보려고 한다.

7을 깊이 0이라고 한다면, 깊이 3에 해당하는 2는 깊이 4에서 최대값을 찾기 위해 2가 다음 깊이에서 가질 수 있는 두개의 값중 가장 큰 값을 선택해야 한다.

깊이 3에 해당하는 7도 깊이 4에서 최대값을 찾기 위해 7이 가질 수 있는 두개의 값 5와 2중에서 가장 큰 값을 선택해야 한다.

결국은 모든 경우의 수를 다 계산한 후, 가장 큰 값을 반환하게 되어있다. 그러나 이것은 시간초과가 발생했다. 그 이유는 무엇일까?!

방금 깊이 3에 해당하는 2와 7이 어떻게 깊이 4에서 최대값을 구하는지 확인해봤는데, 여기서 중복적인 계산이 존재하지 않았는가?!

그렇다 깊이 3에 해당하는 2와 7은 공통적으로 5를 계산한다. 그렇다면 깊이 4에 해당하는 5는 깊이 3에서 2와 7중에서 가장 큰 값과 더하면 되지 않을까?

그리고 깊이 3에 해당하는 수는 깊이 2에서 ....?! 이렇게 문제를 작은 단위로 쪼개서 풀 수 있는 경우에는 동적계획법을 사용할 수 있다.

동적계획법을 사용하면 중복적인 계산을 제거할 수 있기 때문에 시간초과 문제가 해결될 수 있다. 그렇더라!!

처음에 너무나도 빠르게 브루트포스-완전탐색을 사용해서 문제를 풀었고, 통과 통과 통과를 보면서 별거 아니자나? 라고 생각을 했다.

그러다가 순식간에 시간초과 두두두두 떳다... 그리고 잠시 마라톤 연습을 하면서 뛰는동안.. 갑자기... 이렇게 하면 되지 않을까? 라는 생각이 들었고...

운이 좋게도 맞았다! 좋았다! 뇌를 뜨겁게 대피니 생각이 잘 나는 것 같다.. 근데... 피곤하다.... 그렇더라!! 끝!