알고리즘 문제 풀이를 블로그에 올리는 이유는 풀이, 코드를 기록하기 위함이니
앞으로 문제를 다 긁어오기보다 링크만 두고 풀이가 잘 보이도록 포스팅 할 예정입니다!
이 문제는 위 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아 최대 숫자 합을 반환하는 문제이다.
public class Solution {
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("top-down 풀이 : " + solution1(triangle));
}
//top-down
public static int solution1(int[][] triangle) {
// 1. 기본값 초기화 //
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];
}
// 2. 동적계획법 //
for(int i = 2; i < triangle.length; i++) {
for(int j = 1; j < i; j++) {
dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
}
}
// 3. 최대값 반환 //
int max = 0;
for(int i = 0; i < dp.length; i++) {
max = Math.max(max, dp[dp.length - 1][i]);
}
return max;
}
}
public class Solution {
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("bottom-up 풀이 : " + solution2(triangle));
}
//bottom-up
public static int solution2(int[][] triangle) {
for(int i = triangle.length-2; i >= 0; i--) {
for(int j = 0; j < triangle[i].length; j++) {
triangle[i][j] += Math.max(triangle[i+1][j],triangle[i+1][j+1]);
}
}
return triangle[0][0];
}
}