[JAVA] 정수 삼각형 (코딩테스트 고득점 Kit [ 동적계획법(DP)]) - LEVEL3

📂문제 설명

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

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

 

제한사항

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

입출력 예

triangleresult

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

30

 

---

📂아이디어 및 알고리즘(문제 풀이)

• 위에서 아래로 내려갈때 왼쪽과 오른쪽을 비교하여 합이 더 큰쪽으로 내려가며 최댓값을 찾아야한다.
• 하지만 내려가면서 최댓값을 골라서만 내려갈 수 없기 때문에 반대로 밑에서 위를 선택하는 방법으로 가야한다.
  • ex) 4번째 줄에 7은 위에 3번째줄에서 8과 1중 누적된 값이 큰값과 더해서 DP값을 늘려나간다. 
  • DP 초기값으로 맨 위에 숫자부터 왼쪽 줄과 오른쪽 줄을 더해주어 만들어 준다.
  • for문에서 DP[i][0] 과 DP[i][i]를 먼저 구해준다.
• 두번째 for문에서 Math.max를 통해 현재 triangle[i][j] 와 (i-1)줄의 DP값과 더했을때 더 큰값을 DP[i][j]에 저장한다.
• 마지막으로 DP의 마지막줄을 순회하면서 가장 큰값을 찾아서 출력해주면 최댓값을 구할 수 있다.  

📂소스 코드

class Solution {

	 public int solution(int[][] triangle) {
	        int n = triangle.length;

			int dp[][] = new int[n][n];
	        dp[0][0] = triangle[0][0];
	        
	        //가장 왼쪽 줄과 오른쪽 줄을 dp로 계산해 준다. 
	        for(int i=1;i<n;i++) {
	        	dp[i][0] = dp[i-1][0] + triangle[i][0]; 
	        	dp[i][i] = dp[i-1][i-1] + triangle[i][i];
	        }
	        
	        for(int i=2;i<n;i++) {
	        	for(int j=1;j<i;j++) {
	        		dp[i][j] = Math.max(dp[i-1][j-1]+triangle[i][j], dp[i-1][j]+triangle[i][j]);
	        	}
	        }
	        
	        // 삼각형 마지막줄에서 제일 큰 수 찾기 
	        for(int x : dp[n-1]) if(max<x) max=x; 	        
	        return max;
	 }
}

 

📂후 기

 

DP를 쓰는 가장 기본적인 문제에 해당한다. DP를 바로 생가하지 못하면 매번  비교하며 찾아야해서 시간초과 문제가 되기 싶다.  [ 후우~ .☄ 쉬고 싶다아 ]