[프로그래머스] 정수 삼각형(Java, Lv.3)

문제

 

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다.

아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 

 

입출력 예 

 

풀이

동적계획법(DP) 사용

 

 

2차원 배열 dp 값 설정 

dp의 원소 값 중 가장 큰 값 출력 

 

최종  코드

public static int solution(int[][] triangle) {

        System.out.println("정수 삼각형");

        int len = triangle.length;

        // 1. dp 초기화

        int[][] dp = new int[len][len];

        dp[0][0] = triangle[0][0];

        // 1-1. 첫번째 요소 초기화 [i][0]

        for (int i = 1; i < len; i++) {

            dp[i][0] = triangle[i][0] + dp[i - 1][0];

        }

        // 2. 동적 계획법

        // 2-2. 첫번째 요소를 제외한 모든 값 초기화

        for (int i = 1; i < len; i++) {

            for (int j = 1; j < i + 1; j++) {

                dp[i][j] = triangle[i][j] + Math.max(dp[i - 1][j - 1], dp[i - 1][j]);

            }

        }

        // 3. 최댓값 구하기

        // int max = 0;

        // for (int i = 0; i < len; i++) {

        //     max = Math.max(dp[len - 1][i], max);

        // }

        Arrays.sort(dp[len - 1]);

       

        return dp[len - 1][len - 1];

    }

 

 

 

프로그래머스 문제 

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

프로그래머스