[프로그래머스 / JAVA] 정수삼각형 Lv.3 풀이

문제

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중,

거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 

아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 

예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 

거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

 

제한 사항

삼각형의 높이는 1 이상 500 이하입니다.

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

 

풀이 과정

이 문제는 동적 계획법 알고리즘을 사용하여 문제를 풀어야 합니다.

문제를 해석해보면 위에서 아래로 내려가면서 경로를 합한 값의 최대값을 마지막줄에서 반환하면됩니다.

다만, 대각선 방향으로 왼쪽 오른쪽으로 이동만 가능하며 그림으로 나타내보면 다음과 같습니다.

그리고 마지막에 최댓값인 30이 출력되면 됩니다.

 

이 과정을 코드로 구현한다고 하면

① int x 라는 변수를 2를 할당합니다. (x는 밑으로 내려갈수록 하나씩 늘어납니다.)

② 1부터 배열의 길이까지 for문으로 반복하는데 1부터 하는 이유는 7은 숫자가 하나밖에 없기 때문입니다.

③ 이중 for문으로 x 까지 반복하여 가로의 경로를 이동할 수 있도록 합니다.

④ if 조건문을 넣어서 j가 0인 경우 그 위의 값을 자신의 값과 더합니다. ( j는 가로방향, i는 세로 방향)

⑤ else if 에 (j == i) 값이 같을 경우 자신으로부터 왼쪽 위의 최대값을 자신과 더해준다. (맨 오른쪽 값을 말함)

⑥ else는 위의 값 두개중에 최대값을 자신의 값과 더해주는 역할을 한다.

⑦ x값은 값이 하나씩 증가하므로 1씩 증가시킨다.

 

⑧ 마지막으로 각각의 경로로 나온 최대값중에서 가장 큰 값을 answer에 넣으면 된다.

 

전체 코드

import java.util.*;

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

		int x = 2;
		
		for (int i = 1; i < triangle.length; i++) {

			for (int j = 0; j < x; j++) {

				if (j == 0) {
					triangle[i][j] = triangle[i][j] + triangle[i - 1][j];
				} else if (j == i) {
					triangle[i][j] = triangle[i][j] + triangle[i - 1][j - 1];
				} else {
					triangle[i][j] = Math.max(triangle[i - 1][j], triangle[i - 1][j - 1]) + triangle[i][j];

				}
			}
			x += 1;
		}

		int i = triangle.length - 1;
		int arrayNum[] = new int[triangle.length];

		for (int j = 0; j < triangle.length; j++) {
			arrayNum[j] = triangle[i][j];
		}

		int maxValue = Arrays.stream(arrayNum).max().getAsInt();
		answer = maxValue;

		return answer;
	}
	
	public static void main(String[] args) {
		int[][] triangle = {{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
		System.out.println(solution(triangle));
	}
}

 

결과