[level3] 정수 삼각형 JAVA

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

프로그래머스

 

내가 푼 틀린 정답!

class Point {
	int y, x;

	public Point(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}
}
class Solution {
   	static int max;
	
	public int solution(int[][] triangle) {
        
        
        int n = triangle.length-1;
        Point p = new Point(0, 0);
        dp(triangle, p, triangle[0][0], n);
        
        return max;
    }

	private void dp(int[][] triangle, Point p, int sum, int depth) {
	
		if(depth == 0) {
			max = Math.max(sum, max);
			System.out.println("sum : " + sum);
			return;
		}
		
		for(int i = 0; i < 2; i++) {
			int dy = p.y+1;
			int dx = p.x + i;
			Point point = new Point(dy, dx);
			 
			dp(triangle, point, sum+triangle[dy][dx], depth-1);
		}
	}
}

- 이유는 재귀함수를 계속 반복하면서 시간을 초과하게 되는 것

 

 

즉, 계산은 한번씩만 하도록 계산한 값 중 가장 큰 값을 저장하여서 값을 도출해야 하는 것이다.

 

import java.util.*;

class Solution {
      public int solution(int[][] triangle) {
		 	int[][] hap = new int[triangle.length][triangle.length];
	        
	        hap[0][0] = triangle[0][0];
	        
	        for(int i = 1; i < triangle.length; i++) {
	        	//맨 왼쪽
	        	hap[i][0] = hap[i-1][0] + triangle[i][0];
	        	
	        	//중간
	        	for(int j = 1; j <= i; j++) {
	        		hap[i][j] = Math.max(hap[i-1][j], hap[i-1][j-1]) + triangle[i][j];
	        	} 
	        	
	        	//맨 오른쪽
	        	hap[i][i] = hap[i-1][i-1] + triangle[i][i];			
	        }
	        
	        int [] ans = hap[triangle.length-1];
	        
	        Arrays.sort(ans);
 
	        return ans[ans.length-1];
	 }
}