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

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

프로그래머스

• 정수 삼각형

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

 

 

(풀이코드)

class Solution {
    public int solution(int[][] triangle) {
            int answer = 0;
	        int n = triangle.length;
	        int[][] dp = new int[n][];
	        dp[0] = new int[]{triangle[0][0]};
	        int d = 2;
	        for(int i = 1; i< n; i++) {
	        	dp[i]= new int[d];
	        	for(int j = 0; j<d; j++) {
	        		if(j==0) {
	        			dp[i][j] = dp[i-1][j]+triangle[i][j];			
	        		}else if(j==d-1){
	        			dp[i][j] = dp[i-1][j-1]+triangle[i][j];
	        		}else{
	        			dp[i][j] = dp[i-1][j-1]>dp[i-1][j]?dp[i-1][j-1]+triangle[i][j]:dp[i-1][j]+triangle[i][j];
	        		}
	        	}
	        	d++;

	        }
	        for(int t : dp[n-1]) {
	        	answer = t>answer?t:answer;
	        }
	        return answer;
    }
}

 

(코드설명)
// 우선 문제 자체가 동적계획법 파트에 있었기 때문에, dp를 사용해서 풀려고 하였다.

먼저 기본적인 초기값들을 설정해준다. 답을 저장할 answer, triangle의 크기를 저장할 n
그리고 dynamic Programming을 실행할 dp라는 2차원 배열을 선언하여 준다.

그리고 dp[0]에는 traiangle의 가장 꼭대기값을 넣어준다. 비교 대상이 없으므로 이 값을 넣는다.

그리고 이제 2번쨰 뎁스 부터 시작해 반복문을 도릭 위해 d =2 라고 선언해준다. 

그리고 반복문을 이용해서 가게 되는데, 
값들을 비교해보면, 
[0,0]
[1,0][1,1]
[2,0][2,1][2,2]
....
이런 식으로 생겨서 자신의 위의 값들 중에 현재 위치가 i,j라면, 그 위의 dp[i-1][j-1] 과 dp[i-1][j] 값과 비교해서 더 큰 값을 가져오면 dp가 생성된다. 
위의 if 문과 else if문은 처음값이나 끝깞으로 비교대상이 없을 경우를 위해 넣어주었다. 

그리고 회전을 끝냈다면, d++로 한칸 더 뎁스를 늘려준다.

이와 같은 반복문을 돌면서 dp를 모두 채우면 그 값까지 가는데 가장 큰 값이 가장 아래의 dp[n-1]의 행에 저장될 것이고, 

이 값을 

반복문을 돌면서 추출하여 return 해준다.