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

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

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

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

2. 입력

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

3. 예제

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

4. 풀이

2줄의 삼각형을 보았을 때 3의 위치로 올 경우 값은 10(7 + 3)이 되며 8의 위치의 값은 15(7 + 8)가 됩니다.

3의 경우 한줄 위의 왼쪽 값이 없으므로 오른쪽 값인 7에 현재 값 3을 더하여 10이 됩니다.

8의 경우 한줄 위의 오른쪽 값이 없으므로 왼쪽 값인 7에 현재 값 8을 더하여 15가 됩니다.

 

이번에는 3줄의 삼각형을 보았을 때 8의 위치는 18이 되며 1의 위치는 16이 되고 0의 위치는 15가 됩니다.

8의 경우는 한줄 위의 왼쪽 값이 없으므로 오른쪽 값인 10에 현재 값 8을 더하여 18이 됩니다.

1의 경우는 한줄 위의 왼쪽 값과 오른쪽 값 모두가 존재 하므로
왼쪽과 더한 값 11(10 + 1)과 오른쪽과 더한 값 16(15 + 1) 중 큰 값이 해당 위치의 값이 되므로 16(MAX(11, 16))이 됩니다.

0의 경우 한줄 위의 오른쪽 값이 없으므로 왼쪽 값인 15에 현재 값 0을 더하여 15가 됩니다.

 

위 두번의 과정으로 정리 할 수 있는 점화식이 생깁니다.

1. DP 삼각형의 가장 왼쪽의 값은 한줄 위의 가장 왼쪽 값에 현재 값을 더한 값이 된다.
   2번째 줄 10 = DP배열의 1번째 줄 가장 왼쪽 값 7 + triangle배열의 2번째 줄 가장 왼쪽 값 3
   3번째 줄 18 = DP배열의 2번째 줄 가장 왼쪽 값 10 + triangle배열의 3번째 줄 가장 왼쪽 값 8
   DP[i][0] = DP[i-1][0] + triangle[i][0]이 됩니다.
   
   
2. 삼각형의 가장 오른쪽의 값은 한줄 위의 가장 오른쪽 값에 현재 값을 더한 값이 된다.
   2번째 줄 15 = DP배열의 1번째 줄 가장 오른쪽 값 7 + triangle배열의 2번째 줄 가장 오른쪽 값 8
   3번째 줄 15 = DP배열의 2번째 줄 가장 오른쪽 값 15 + triangle배열의 3번째 줄 가장 오른쪽 값 0
   DP[i][i] = DP[i-1][i-1] + triangle[i][i]이 됩니다.
   
   
3. 삼각형의 1번과 2번을 제외한 나머지는 한줄 위의 오른쪽 값과 왼쪽값 중 큰 값에 현재 값을 더한 값이 된다.
   3번째 줄 16 = DP배열의 2번째 줄 왼쪽 값 10 + triangle배열의 3번째 줄 값 1과 DP배열의 2번째 줄 오른쪽 값 15 + triangle배열의 3번째 줄 값 1 중 큰 값인 16(MAX(11, 16))이 된다.
   DP[i][i] = Max(DP[i - 1][j - 1], DP[i - 1][j]) + triangle[i][j]가 됩니다.

 

5. 코드

전체 코드는 Git에 있습니다.

int answer = 0;
int[][] temp = new int[triangle.length][triangle[triangle.length-1].length];
temp[0][0] = triangle[0][0];

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

return answer;