[프로그래머스 Level.3] 정수 삼각형 (동적계획법(Dynamic Programming)) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 동적계획법(Dynamic Programming) > 정수 삼각형

 

 

 

문제 설명

 

 

 

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

 

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

 

 

 

 

제한사항

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

 

 

입출력 예

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

 

 

 

 

 

나의 코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        int[][] dp = new int[triangle.length][triangle[triangle.length-1].length];
        dp[0][0] = triangle[0][0];
        
        for(int i=1; i<triangle.length; i++) {
            dp[i][0] = triangle[i][0] + dp[i-1][0];
            
            for(int j=1; j<triangle[i].length; j++) {
                dp[i][j] = triangle[i][j] + Math.max(dp[i-1][j-1], dp[i-1][j]);
            }
        }
        
        for(int i=0; i<triangle.length; i++) {
            answer = Math.max(answer, dp[triangle.length-1][i]);
        }
        
        return answer;
    }
}

 

풀이

1. 동적계획법(DP)를 이용하여 문제를 풀었다.
2. 삼각형을 직각삼각형으로 생각하고 문제를 풀면 된다. (▲ -> ◣)
3.  int형 2차원 배열 dp를 삼각형의 높이, 삼각형의 밑변의 길이로 생성한다.
4. 삼각형의 제일 위의 꼭짓점(dp[0][0])을 triangle[0][0]으로 저장한다.
5. 이제 triangle의 높이만큼 돌면서 제일 왼쪽(열 인덱스가 0) dp는 바로 위(i-1)까지의 dp와 더하고 나머지는 다시 해당 행의 triangle 변의 길이 만큼 for문을 돌면서 해당 행 점의 바로 위까지의 dp와 바로 왼쪽 위 대각선까지의 dp와 비교하여 큰 값을 해당 행의 점인 triangle[i][j]와 더하면서 dp[i][j]를 채워간다. 
6. dp를 다 채웠으면 맨 마지막 밑변(dp[tiranlge.length-1][i])의 dp 값들을 비교하여 최댓값을 answer에 저장하고 반환한다.
7.  

dp[0][0] = triangle[0][0]	dp[0][1] = 0	dp[0][2] = 0	dp[0][3] = 0	dp[0][4] = 0
dp[1][0] = dp[0][0] + triangle[1][0]	dp[1][1] = triangle[1][1] + max(dp[0][0], dp[0][1]=0)	dp[1][2] = 0	dp[1][3] = 0	dp[1][4] = 0
dp[2][0] = dp[1][0] + triangle[2][0]	dp[2][1] =  triangle[2][1] + max(dp[1][0], dp[1][1])	dp[2][2] = triangle[2][2] + max(dp[1][1], dp[1][2]=0)	dp[2][3] = 0	dp[2][4] = 0
dp[3][0] = dp[2][0] + triangle[3][0]	dp[3][1] =  triangle[3][1] + max(dp[2][0], dp[2][1])	dp[3][2] = triangle[3][2] + max(dp[2][1], dp[2][2])	dp[3][3] = triangle[3][3] + max(dp[2][2], dp[2][3]=0)	dp[3][4] = 0
dp[4][0] = dp[3][0] + triangle[4][0]	dp[4][1] =  triangle[4][1] + max(dp[3][0], dp[3][1])	dp[4][2] = triangle[4][2] + max(dp[3][1], dp[3][2])	dp[4][3] = triangle[4][3] + max(dp[3][2], dp[3][3])	dp[4][4] = triangle[4][4] + max(dp[3][3] + dp[3][4]=0)

 

따라서 문제로 주어진 삼각형으로 봤을 때
삼각형의 한 행의 맨 왼쪽 변의 점은 바로 위 행의 맨 왼쪽 점 dp 값 + 자신의 triangle 값이고

삼각형의 한 행의 맨 오른쪽 변의 점은 바로 위 행의 맨 오른쪽 점 dp 값 + 자신의 triangle 값이고

나머지 중간의 점들은 자기를 사이로 두는 바로 위 행의 dp 값 중 큰 값 + 자신의 triangle 값이 된다.