위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
제한사항
삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
🌄 예시
🌄 풀이 설명
해당 문제는 동적 계획법을 사용하는 문제이다.
위의 사진의 표처럼 주어진 삼각형을 이차원 배열 표로 나타내었다.
7 + 3 + 8 + 2 + 4 혹은 7 + 3 + 8 + 2 + 5 처럼 각 위치의 삼각형의 값을 더 해주고, 그 값들 중 가장 큰 값을 구하는 문제이다.
위의 표를 다시 참고하면, DP 삼각형을 하나 만들어 주었다.
{0,0} 은 7이다.
{1,0} 은 7 + 3 으로 10이다.
{1,1} 은 7 + 8 로 10이다.
{2,0} 은 7 + 3 + 8 으로 18이다.
{2,1} 은 7 + 3 + 1과 7 + 8 + 1 두 개의 방식으로 가능한 데, 이 문제는 가장 큰 값을 찾는 문제이므로 두 수 큰 값인 7 + 8 + 1을 넣어 주었다. 여기서 알 수 있는 것은 {2 -1, 1-1}위치의 값과 {2 -1, 1}위치의 값 중 큰 값에 삼각형의 해당 위치인 {2,1} 값을 더 해준 것이다.
{2,2} 는 7 + 8 + 0 으로 15이다.
dp 이차원 배열을 생성해준다.
길이는 정수 삼각형의 길이와 똑같이 생성한다.
그리고 {0,0} 위치에 정수삼각형의 {0,0} 값을 넣어준다.
public static int solution(int[][] triangle) {
int answer = 0;
int[][] dp = new int[triangle.length][triangle.length];
dp[0][0] = triangle[0][0];
return answer;
}
정수 삼각형의 길이만큼 반복문을 돌며 dp 배열에 값을 넣어준다.
좌측은 비교할 좌측 대각선 위의 값이 없으므로, 자신의 위에 위치한 값에 정수 삼각형의 현재 위치 값을 더해준다.
우측은 자신의 위에 위치한 값이 없으므로 (0) 자신의 좌측 대각선 위의 값에 정수 삼각형의 현재 위치 값을 더해준다.
중앙에 여러 값이 올 수 있으므로 반복문을 돌려준다.
반복문 안에서는 자신의 우측 대각선 위의 값과 자신의 위의 값 중 큰 값에 정수 삼각형의 현재 위치 값을 더해준다.
public static int solution(int[][] triangle) {
int answer = 0;
...
for (int i = 1; i < triangle.length; i++) {
/* 좌측 */
dp[i][0] = dp[i - 1][0] + triangle[i][0];
/* 우측 */
dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
/* 중앙 */
for (int j = 1; j < i ; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
}
}
return answer;
}
정수 삼각형에서 가장 큰 값은 정수 삼각형 길이 - 1의 행, 즉 가장 마지막 행의 값에 있을 것이다.
그렇기 때문에 반복문을 돌면서 해당 행의 열 값들을 확인하면서 가장 큰 값을 answer에 담아준다.
그리고 해당 값을 리턴해준다.
public static int solution(int[][] triangle) {
int answer = 0;
...
for (int i = 0; i < triangle.length; i++) {
answer = Math.max(answer, dp[triangle.length -1][i]);
}
return answer;
}
🌄 최종 풀이
public static int solution(int[][] triangle) {
int answer = 0;
int[][] dp = new int[triangle.length][triangle.length];
dp[0][0] = triangle[0][0];
for (int i = 1; i < triangle.length; i++) {
/* 좌측 */
dp[i][0] = dp[i - 1][0] + triangle[i][0];
/* 우측 */
dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
/* 중앙 */
for (int j = 1; j < i ; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
}
}
for (int i = 0; i < triangle.length; i++) {
answer = Math.max(answer, dp[triangle.length -1][i]);
}
return answer;
}
