오늘은 프로그래머스에서 동적계획법 문제 중 정수 삼각형 문제 풀이를 하겠습니다. 오늘의 문제인 정수 삼각형을 풀 수 있는 언어가 한정적이므로, 오늘 문제는 두번째 선호 언어인 Java를 활용하여 문제 풀이를 해볼 예정입니다. 그럼 정수 삼각형 문제 풀이 함께 시작해보겠습니다.
프로그래머스 > 동적계획법 > 정수 삼각형 문제 풀이
¡ 문제 정보
문제명: 정수 삼각형
문제 난이도: Level 3
문제 푼 사람 수: 13487명
사용 가능 언어: 3개 (Java 사용)
¡ 문제 설명
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
삼각형 꼭대기에서 바닥까지 거쳐간 숫자의 최댓값 구하기
Input
triangle: 숫자로 만들어진 삼각형 배열
Output: 삼각형 꼭대기에서 바닥까지 거쳐간 숫자의 최댓값
¡ 제한 사항
º 삼각형의 높이는 1 이상 500 이하입니다. º 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
1. 삼각형의 각 지점 별 합산 최댓값을 저장할 배열을 만든다. 2. 삼각형 꼭대기 행부터 바닥 행까지 순회한다. 3. 아래로 내려오면서 거쳐갈 수 있는 경로의 수에 대하여 계속 합산하여 배열에 저장한다. 3-1. 맨 뒤에서부터 합산한 결과를 저장한다. 4. 마지막에 합산한 모든 값 중 최댓값을 반환한다.
위의 알고리즘에서 가장 키포인트는 3-1입니다. 각 행에 대해서 맨 뒤에서부터 합산하는 이유는 바로 윗 행까지 합산된 결과가 저장된 배열의 길이는 현재 행보다 1이 작습니다. 그렇기 때문에 현재 행의 합산 최댓값을 저장하기 위해 비어있는 제일 마지막 열부터 채우는 방식으로 메모리를 최소한 활용하는 알고리즘으로 만들어보았습니다.
위 알고리즘의 이해를 돕기 위해 입출력 예제의 5행까지의 합산 결과를 이미지화하여 보았습니다.
이 때, 각 행의 합산 최댓값의 길이는 직전 행의 합산 최댓값의 길이보다 1씩 증가함을 확인할 수 있습니다. 그렇기에 맨 뒤에서부터 합산한 최댓값을 구하여 입력한다면, 하나의 배열로 값 저장을 완료할 수 있습니다.
¡ 코드 구현
class Solution {
public int solution(int[][] triangle) {
// 1. 삼각형의 각 지점 별 최대 합산 값을 저장할 배열을 만든다.
int sumResult[] = new int[triangle.length];
sumResult[0] = triangle[0][0];
// 2. 삼각형 꼭대기 행부터 바닥 행까지 순회한다.
for(int rowIndex = 1; rowIndex < triangle.length; rowIndex++) {
// 3-1. 맨 뒤에서부터 합산한 결과를 저장한다.
for(int columnIndex = triangle[rowIndex].length - 1; columnIndex >= 0; columnIndex--) {
// 3. 아래로 내려오면서 거쳐갈 수 있는 경로의 수에 대하여 계속 합산하여 배열에 저장한다.
if(columnIndex == 0) {
sumResult[columnIndex] += triangle[rowIndex][columnIndex];
} else if(columnIndex == triangle[rowIndex].length - 1) {
sumResult[columnIndex] = sumResult[columnIndex-1] + triangle[rowIndex][columnIndex];
} else {
sumResult[columnIndex] = Math.max(sumResult[columnIndex-1] + triangle[rowIndex][columnIndex], sumResult[columnIndex] + triangle[rowIndex][columnIndex]);
}
}
}
// 4. 마지막에 합산한 모든 값 중 최댓값을 반환한다.
return getMaxResult(sumResult);
}
int getMaxResult(int[] list) {
int max = 0;
for(int i = 0; i < list.length; i++) {
if(max < list[i]) {
max = list[i];
}
}
return max;
}
}
¡ 채점 결과
오늘도 프로그래머스에서 정수 삼각형 문제 풀이를 해보았으며, 채점 결과는 정확성 테스트 케이스 10개, 효율성 테스트 케이스 10개 모두 통과하여 문제 풀이를 완료하였습니다.
댓글