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

문제 링크

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

문제 요약

• 위에서 아래로 규칙에 따라 숫자를 합했을 때 맨 밑에 모이는 수 중 가장 큰 수를 구한다

풀이 흐름

• 그림의 삼각형을 왼쪽 직각을 가지는 직각 삼각형이라고 생각한다
  7
  3 8
  8 1 0
  2 7 4 4
  4 5 2 6 5
  위에서 아래로 내려갈 땐 바로 아래, 또는 대각선으로 오른쪽 아래로 내려가는 셈이니까 현재 위치가 [i, j] 이면 다음 위치는 [i+1, j], [i+1, j+1] 이 된다.
  그럼 현재 위치로 올 수 있는 이전 위치는 [i-1, j-1], [i-1, j].
  현재 위치 이전까지 어떤 과정을 거쳤는지는 모르겠지만 현재 위치에서 선택할 수 있는 최선의 위치는 두가지 이전 위치 중 더 합이 큰 경우를 선택하는 것.

• 다른 풀이 : 밑에서부터 위로 꺼꾸로 돌아가는 풀이
  -> edge값 처리 따로 안해도 됨. 마지막 n개 중 max를 찾는 연산 없어도 됨

---

코드
풀이언어 : JAVA

public int solution(int[][] triangle) {

        int last = triangle.length;
        int[][] dp = new int[501][501];
        
        dp[1][1] = triangle[0][0];
        for(int row = 2; row <= last; ++row) {
        	for(int col = 1; col <= row; ++col) {
        		int mmax = Math.max(dp[row-1][col-1], dp[row-1][col]);
        		dp[row][col] = triangle[row-1][col-1] + mmax;
        	}
        }
        
        int answer = (int)Arrays.stream(dp[last])
        		.max()
        		.getAsInt();

        return answer;
    }

풀이2

public int solution(int[][] triangle) {
	int answer = 0;
    
    for(int i = triangle.length-2; i>=0; i--){
    	for(int j=0;j<triangle[i].length;j++){
        	int left = triangle[i][j] + triangle[i+1][j];
            int right = triangle[i][j] + triangle[i+1][j+1];
            
            triangle[i][j] = Math.max(left, right);
        }
    }
    
    return triangle[0][0];
}