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

문제설명

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

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

 

해결 방법

동적계획법(DP, Dynamic Programming)으로 해결할 수 있는 문제로,

 

문제에서 1번째 층에서 n번째 층으로 갔을 때, 합의 최댓값을 구하라고 했다.

 

이 말은 i층에서 i+1층으로 갈 때 갈 수 있는 두 값중 큰 값을 거쳐야한다는 말과 같다.

 

즉, i층은 i+1층의 인접한 두 값 중 최대값을 선택할 것이다.

 

이러한 방식으로 거꾸로 n층에서 n-1층으로 올라간다고 생각했을 때, 인접한 두 값 중 최대값을 선택해 올라간다.

 

예를 들어, 아래와 같은 삼각형이 주어졌다고 생각하자,

 

7

3 8

8 1 0

2 7 4 4 

4 5 2 6 5

 

위의 삼각형이 있을 때 밑에서부터 경로를 찾아나간다.

i행의 j번째까지의 총 이동거리는 (i+1)행의 j번째와 (j+1)번째 경로까지의 최대값 + i번째 j번째의 거리이다.

 

S[i][j] = max(D[i+1][j], D[i+1][j+1]) + D[i][j]; 

(D[i][j] : 경로의 이동거리    S[i][j] : 총 이동거리)

 

7

3 8

8 1 0

2 7 4 4  <- 시작점

4 5 2 6 5

------------------

7

3 8

8 1 0

7 12 10 10

------------------

7

3 8

20 13 10

------------------

7

23 21

------------------

30

 

비슷한 유형으로 백준의 정수 삼각형 문제가 있다.

 

https://dheldh77.tistory.com/102

[백준] 1932번 - 정수 삼각형

 

JAVA

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