[프로그래머스] 정수 삼각형 -Java

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

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

import java.util.Arrays;
class Solution {
	    public int solution(int[][] triangle) {
	        
	        for(int i=1; i<triangle.length; i++) {
	        	for(int j=0; j<triangle[i].length; j++) {
	        		if(j==0) triangle[i][j]+=triangle[i-1][j];
	        		else if(i==j) triangle[i][j]+=triangle[i-1][j-1];
	        		else triangle[i][j]+=Math.max(triangle[i-1][j],triangle[i-1][j-1]);
	        	}
	        }
	        
	        return Arrays.stream(triangle[triangle.length-1]).max().getAsInt();
	    }
	}

소요시간 : 15분

 

엄청 쉬운 dp문제입니다!

이렇게 입력이 주어진다면

            7

       10     15

    18    16    15

  20   25    20   19

24  30   27    26   24  이런식으로 계산을 해주면 됩니다.

 

만약 j가 0이라면 무조건 [i-1][j] 의 값을 받아와서 자기자신과 더합니다.

만약 j가 i와 같다면(맨 오른쪽자리) 라면 무조건 [i-1][j-1] 의 값을 받아서 자기자신과 더합니다.

 

만약 위의 두 케이스가 아니라면 [i-1][j]와, [i-1][j-1]의 값 중 더 큰것을 받아서 자기 자신과 더합니다.

 

이렇게 쭉 하다가 마지막 행에서 가장 큰 값을 뽑아주면 됩니다!