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

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

프로그래머스

 

요구사항 분석

삼각형 배열 triangle[][]이 주어진다.

가장 위 꼭짓점에서 밑변까지 아래칸 i, i+1로만 이동이 가능할 시 거쳐간 숫자의 최대 합을 구해라.

1 <= 삼각형의 높이 <= 500

0 <= 삼각형을 이루고 있는 숫자 <= 9999

 

사고의 흐름

삼각형의 높이로 보아, triangle의 모든 요소는 최악의 경우 1~500 250*501개이다. == 충분한 시간

완전 탐색=> 시간 초과

dp인가?

1. 하나의 최적해를 구하기 위해서 중복되는 부분 문제들이 필요한 부분이 나오는가?

dp[2][0]의 최적해를 찾기 위해서는 Math.max(dp[2][0], dp[1][0] + dp[2][0]) 즉, dp[2][0]을 구하기 위해서는 dp[1][0]을 구하는 부분 문제가 필요하다. yes!

2. 현재의 문제는 여러 개의 최적해를 가진 부분 문제로 나뉘는가?

위에서 볼 수 있듯, yes!!

dp이다.

 

이제 풀어보자.

1. 최적해의 구조의 특징을 찾는다.

최상단 꼭짓점에서 밑변까지 도달하기 위해 지나온 모든 수들을 a1 a2 ... 으로 표현한다.

{a1 + a2 + a3 + ... + an} = {an} + {a1 + a2 + a3 + ... + an-1} = {an + an-1 + an-2} + {an-3 + ... + a3 + a2 + a1}

만약 a1 + ... + an이 최적해라면, 위의 식처럼 여러 개의 최적해의 부분 문제로 나뉘는 것을 볼 수 있다.

2. 최적해의 값을 재귀적으로 정의한다.

{a1 + a2 + ... + an}의 값(최적해)를 dp[n]으로 정의한다.

k < n일때,

dp[1, n] = dp[1, n-k] + dp[n-k+1, n]

n == 1일때,

dp[1,1] = triangle[1] 

즉, 점화식이 나오는 것이다.

3. 최적해의 값을 계산한다.

상향식, 하향식 두 방법 중 상향식이 내 기준으로 편하기 때문에, 상향식으로 계산을 해준다.(재귀의 방법을 쓰는 하향식은 아직 어렵다....)

4. 계산된 정보들로부터 최적해를 구성한다.

triangle.length-1번의 인덱스 즉, dp[][]의 가장 마지막 배열은 각 요소까지 도달할 때의 최댓값들을 갖고 있다.

for문을 돌려 max값을 가져오자.

 

코드

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

 

============================================================================================

비교적 쉬운 문제였다. 20분만에 푼 것 같다.