[ 알고리즘 ] 코딩 - Programmers - 정수삼각형.java

---

문제 링크

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

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

---

개요

프로그래머스 - Level3 - (자바) 정수삼각형 - 동적 계획법(DP)의 기본

---

로직

Step 01. 가장 아래의 배열부터 시작한다 Step 02. 2개의 요소를 비교해가며 더 큰 숫자만을 바로 위 배열의 요소에 더해준다 Step 03. 가장 꼭대기에 닿을때까지 반복한다 Step 04. 꼭대기가 정답 위 그림의 과정을 반복한다!

---

코드

class Solution {
	    public int solution(int[][] triangle) {
	    	int size = triangle.length;
	    	
	    	for(int i = size-1; i >= 0; i--) { // 전체 배열의 높이
	    		for(int j = 0; j < triangle[i].length-1;j++) { // 현재 층의 배열의 개수만큼
	    			// 크기 비교
	    			int max = triangle[i][j] > triangle[i][j+1] ? triangle[i][j] : triangle[i][j+1];
	    			if(i-1 < 0) break; // 꼭대기 넘어가면 멈춰!!
	    			triangle[i-1][j] += max; // 값 갱신
	    		}
	    	}
	    	int answer = triangle[0][0]; // 꼭대기가 정답
	        return answer;
	    }
	}