[프로그래머스]DP:정수 삼각형(java)

문제보러가기

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

 

이문제는 DP의 개념과 배열로 삼각형을 접근하는 방법만 알면 어렵지않게 풀 수 있는 문제였던것 같다.

 

 

 

 

 

문제풀이

-DP배열에 이전까지와 현재 값을 더한것중 큰것을 넣는다.

-위의 그림처럼 배열이 생성되고 따라서 빨간 화살표부분이 DP[i][j]이면 DP[i-1][j-1],DP[i-1][j]에서 내려올 수 있는 것이다.

-따라서 DP[i][j] =Math.max(dp[i-1][j-1], dp[i-1][j])+triangle[i][j] 가 된다.

-여기서 고민해 봐야할 것은 삼각형 면들에 있는 즉 j==0일때와 j==i일때의 경우에는 양쪽에서 내려오는것이 아닌 한쪽에서만 내려올 수 있다

-따라서 j==0 일때, dp[i][j] = dp[i-1][j]+triangle[i][j] 

-         j==1 일때,dp[i][j] = dp[i-1][j-1]+triangle[i][j] 식으로 계산 할 수 있다.

-마지막으로 삼각형의 밑변에 해당하는 마지막 배열에서 가장 큰 수가 답이 된다.

 

 

 

class Solution {
    public int solution(int[][] triangle) {
       int[][] dp = new int [triangle.length][triangle[triangle.length-1].length];
		int max=0;
        //꼭짓점 dp
		dp[0][0]=triangle[0][0];
		for(int i=1;i<triangle.length;i++){
			for(int j=0;j<triangle[i].length;j++) {
            	//각각 경우마다 어느 경로로 온 값이 큰지 판단해서 넣어줌
				if(j==0) {
					dp[i][j] = dp[i-1][j]+triangle[i][j];
				}
				else if(j==i) {
					dp[i][j] = dp[i-1][j-1]+triangle[i][j];
				}else{					
					dp[i][j]=Math.max(dp[i-1][j-1], dp[i-1][j])+triangle[i][j];
				}
                //삼각형의 밑변 배열일 경우 max값을 찾아서 답으로 출력
				if(i==triangle.length-1) {
					max = Math.max(max, dp[i][j]);
				}
			}
		}
        return max;
	}
}