[programmers] 정수 삼각형

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

프로그래머스

 

---

< 정수 삼각형 >

 

문제 풀이 (Java)

class Solution {
	public int solution(int[][] triangle) {
		int answer = 0;

		int dp[][] = new int[triangle.length][triangle[triangle.length - 1].length];

		dp[0][0] = triangle[0][0];

		for (int i = 0; i < triangle.length - 1; i++) {
			for (int j = 0; j < triangle[i].length; j++) {
				dp[i + 1][j] = Math.max(triangle[i + 1][j] + dp[i][j], dp[i + 1][j]);
				dp[i + 1][j + 1] = Math.max(triangle[i + 1][j + 1] + dp[i][j], dp[i + 1][j + 1]);
			}
		}

		for (int i = 0; i < triangle[triangle.length - 1].length; i++) {
			answer = Math.max(answer, dp[triangle.length - 1][i]);
		}

		return answer;
	}
}

 

거쳐간 숫자의 합을 구하기 위해 dp 배열을 선언한다. 0번째 행에는 원래 값을 저장하고 0번째 행부터 마지막 행 전까지 탐색한다. 이때, 다음 행의 같은 열과, 다음 행의 다음 열에 현재 값을 더했을 때 최댓값을 dp에 저장한다. 

 

최종 마지막 행을 살펴보며 최댓값을 answer에 저장한 후 answer을 반환한다. 

---

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges