프로그래머스 정수 삼각형

문제

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

 

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

풀이 : 동적 계획법 Dynamic Programming

① 2번째 줄부터 시작 

   이전 단계 값들 중에 가장 큰 값과 현재 갑을 더해서 저장한다.

   이전 단계 값 ( y = 현재 위치 or y = 현재위치 -1) ex) (0,1)의 이전 단계 값 : (0,0) / (1,1)의 이전단계값 : (0,0) / (2,1)의 이전단계 값 : (1,1), (1,0)

② 마지막 단계(리프노드) 값 중 최대값을 출력한다.

 

참조

동적계획법, 위키백과

김찬정,  재귀를 사용하여 간결하여 해결하는 방법 ,질문목록, 정수 삼각형, 프로그래머스

 

구현 JAVA

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {

        for(int i = 1 ; i < triangle.length; i++) {
    		for(int j = 0 ; j < triangle[i].length; j++) {
    			int addValue = 0;
    			if(j < triangle[i-1].length) {
    				addValue = triangle[i-1][j];    				
    			}
    			if(j>0 && triangle[i-1][j-1] > addValue) {
    				addValue = triangle[i-1][j-1];
    			}
    			triangle[i][j] = triangle[i][j]+addValue;
    		}
    	}
    	
    	Arrays.sort(triangle[triangle.length-1]);
    	int answer = triangle[triangle.length-1][triangle.length-1];
    	return answer;
    
    }
}