99클럽 코테 스터디 21일차 TIL

오늘의 학습 키워드

• 동적 프로그래밍 (Dynamic Programming)
• 메모이제이션 (Memoization)
• 삼각형 경로 문제 (Triangle Path Problem)

문제 이해

이 문제는 주어진 삼각형 배열에서 꼭대기에서 시작해 아래로 이동하며 최대 합을 구하는 문제입니다. 아래로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동이 가능합니다. 이 문제의 목표는 가능한 모든 경로 중에서 합이 가장 큰 경로를 찾아내는 것입니다.

나의 풀이

package org.example.p_43105;

public class Main {
    static int[][] memo;

    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));
    }

    private static int solution(int[][] triangle) {
        memo = new int[triangle.length][triangle.length];
        return dfs(triangle, 0, 0);
    }

    private static int dfs(int[][] triangle, int x, int y) {
        if (x == triangle.length) { // 마지막 줄에 도달했을 때
            return 0;
        }
        if (memo[x][y] != 0) { // 이미 방문한 적이 있을 때
            return memo[x][y];
        }
        // 현재 위치의 값과 아래 두 값 중 큰 값을 더함
        memo[x][y] = triangle[x][y] + // 현재 위치의 값
                Math.max(dfs(triangle, x + 1, y), // 왼쪽 아래 값
                        dfs(triangle, x + 1, y + 1)); // 오른쪽 아래 값

        return memo[x][y];
    }
}

풀이 설명

1. 초기화
   • 삼각형 배열의 크기만큼 메모이제이션을 위한 memo 배열을 초기화합니다.
   • solution 메소드에서 dfs 메소드를 호출하여 삼각형의 꼭대기에서부터 탐색을 시작합니다.
2. DFS와 메모이제이션
   • dfs 메소드는 재귀적으로 삼각형의 각 경로를 탐색합니다.
   • x와 y는 현재 위치를 나타내며, 삼각형의 마지막 줄에 도달했을 때 0을 반환합니다.
   • 이미 계산된 경로가 있을 경우(memo[x][y] != 0), 저장된 값을 반환하여 불필요한 재귀 호출을 방지합니다.
   • 현재 위치의 값(triangle[x][y])에 아래로 이동했을 때 가능한 두 경로의 최대 값을 더하여 memo[x][y]에 저장합니다.
   • 이 방식으로 꼭대기에서 시작해 각 경로의 최대 값을 재귀적으로 계산하며, 결과적으로 가장 큰 합을 구할 수 있습니다.
3. 결과 반환
   • 재귀 호출을 마치고, solution 메소드는 최종적으로 dfs의 반환 값을 출력합니다. 이 값이 삼각형 꼭대기에서 바닥까지 이어지는 경로 중 가장 큰 합입니다.