[프로그래머스] 레벨3 정수 삼각형

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

코딩테스트 연습 - 정수 삼각형

 

DP 문제의 특징은 한 번 규칙성을 발견하면 코드로 구현하기는 생각보다 어렵지 않다는 것 같다. 이 문제 같은 경우에도 삼각형의 생김새를 배열과 연관지어서 생각하는 게 좀 낯설었지만, 막상 구현은 간단한 문제였다.

 

1. 최대 크기만큼 memoization할 배열(dp)을 만든다.

2. 인덱스를 3개의 경우로 나눠 dp배열의 값들을 채워나간다.

   2-1. 각 줄의 맨 왼쪽일 경우 : 바로 윗 줄의 같은 인덱스 값만 선택

   2-2. 각 줄의 맨 왼쪽일 경우 : 바로 윗 줄의 인덱스-1한 값만 선택

   2-3. 각 줄의 맨 오른쪽일 경우 : 바로 윗 줄의 같은 인덱스, 인덱스-1한 값 중 최대값을 선택

3. 맨 마지막 줄에 계산된 값 중, 가장 큰 값을 결과 출력한다.

 

---

문제 및 입출력

 

---

코드

class Solution
{
    public int solution(int[][] triangle)
    {
        // 최대 크기로 dp배열 설정
        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++)
        {
            for(int j=0; j<triangle[i].length; j++)
            {
                // 각 줄의 맨 왼쪽일 경우 : 바로 윗 줄의 같은 인덱스 값만 선택
                if(j==0)
                {
                    dp[i][j] = triangle[i][j] + dp[i-1][j];
                }
                // 각 줄의 맨 왼쪽일 경우 : 바로 윗 줄의 인덱스-1한 값만 선택
                else if(j==triangle[i].length-1)
                {
                    dp[i][j] = triangle[i][j] + dp[i-1][j-1];
                }
                // 각 줄의 맨 오른쪽일 경우 : 바로 윗 줄의 같은 인덱스, 인덱스-1한 값 중 최대값을 선택
                else
                {
                    dp[i][j] = triangle[i][j] + Math.max(dp[i-1][j], dp[i-1][j-1]);
                }
            }
        }
        
        // 맨 마지막 줄에 대해 최대값을 비교한 후 출력
        int answer = Integer.MIN_VALUE;
        
        for(int j=0; j<dp[dp.length-1].length; j++)
        {
            answer = Math.max(dp[dp.length-1][j], answer);
        }
        
        return answer;
    }
}