[프로그래머스] 정수 삼각형 (DFS+메모이제이션)

문제 소개

풀었던 정수 삼각형 - 프로그래머스 문제 DFS로 정리합니다.
이 문제는 삼각형 형태로 주어진 숫자들 중 꼭대기에서 바닥까지 이동하면서 만들 수 있는 최대 합을 구하는 DP 유형의 문제입니다.

DP 점화식을 DFS로 떠올린 적이 많아서 이번엔 역으로 해봤습니다.

문제 링크: 정수 삼각형 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. DFS로 모든 경로를 탐색
2. 하지만 경로가 많기 때문에 중복 호출을 방지하기 위해 메모이제이션 적용
3. (i, j) 위치에서의 최대합을 기억하고, 다음 호출에서 바로 반환

---

해결 과정 및 코드

핵심 아이디어

1. DFS로 (i, j)에서 아래로 내려가는 두 경로(i+1, j와 i+1, j+1)를 모두 탐색
2. 각 위치에서 내려간 경로 중 더 큰 값을 선택해 누적
3. 이미 계산한 위치는 2차원 배열에 저장(memo[i][j])해서 다시 계산하지 않음
4. 재귀는 꼭대기 (0,0)부터 시작하여 최댓값을 반환

코드

시간 복잡도 :  O(N²)

class Solution {
    int[][] memo;
    int[][] triangle;

    public int solution(int[][] triangle) {
        int h = triangle.length;
        this.triangle = triangle;
        this.memo = new int[h][h];

        return dfs(0, 0); // 꼭대기부터 시작
    }

    private int dfs(int i, int j) {
        // 마지막 줄이면 자기 자신 반환
        if (i == triangle.length - 1) return triangle[i][j];
        // 이미 계산한 값이면 바로 반환
        if (memo[i][j] != 0) return memo[i][j];

        // 아래 두 경로 중 큰 값 선택
        int left = dfs(i + 1, j);
        int right = dfs(i + 1, j + 1);
        memo[i][j] = triangle[i][j] + Math.max(left, right);
        return memo[i][j];
    }
}