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

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

프로그래머스

public class Solution {
	public int solution(int[][] triangle) {
		int preMax = 0, result = 0;
		int r = triangle.length;
		int[][] max = new int[r][r];
		max[0][0] = triangle[0][0];
		
		for(int i=1;i<r;i++) {
			for(int j=0;j<=i;j++) {
				if(j-1<0) {	//왼쪽 위가 없다.
					preMax = max[i-1][j];
				}else {
					//왼쪽 위vs오른쪽 위
					preMax = Math.max(max[i-1][j-1], max[i-1][j]);
				}
				max[i][j] = preMax + triangle[i][j];
				
				//마지막층에서는 그 층에서의 최댓값을 구함
				if(i==r-1) {
					result = Math.max(max[i][j], result);
				}
			}
		}
		
		return result;
	}
}

다시 풀었다!

저번이랑 조금 다르게 풀었네.. 근데 이번에 풀은 솔류션이 다른 사람들 코드에 더 비슷한 것 같다.

 

class Solution {
    public int solution(int[][] triangle) {
        int height = triangle.length;
        int[][] dp = new int[height][height];	//dp[r][c] == (r,c)까지의 최대 누적합
        
        int r = 0, result = 0;
        dp[0][0] = triangle[0][0];
        while(r <= height-2) {
        	for(int i=0;i<=r;i++) {
	        	//왼쪽 아래 
	        	dp[r+1][i] = Math.max(dp[r+1][i], dp[r][i] + triangle[r+1][i]);
	        	//오른쪽 아래 
	        	dp[r+1][i+1] = Math.max(dp[r+1][i+1], dp[r][i] + triangle[r+1][i+1]);
	        	//맨 아랫줄에서 제일 큰 수가 정답 
	        	if(r == height-2) {
	        		result = Math.max(result, dp[r+1][i]);
	        	}
        	}
        	//아래층으로 이동 
        	++r;
        }
        
        result = Math.max(result, dp[height-1][height-1]);
        return result;
    }
}

 

- 추가적으로 풀어볼 문제!

https://www.acmicpc.net/problem/14852

14852번: 타일 채우기 3

풀이는 아래 글 참고해서 깊이 생각해볼 것!

https://blog.naver.com/ndb796/221233586932

21. 다이나믹 프로그래밍 타일링 문제 풀어보기