문제

Programmers - 정수 삼각형

요약

삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능할 때 거쳐간 숫자의 최댓값

접근

문제만 봤을 땐, DFS로 전부 다 탐색할 수 있겠다라는 생각을 했다.
제약 조건을 보니 N이 1~500까지였다. 이를 최악의 경우를 계산해보니 총 노드이 개수는 약 125,000개가 된다. 이를 DFS로 돌리기란 시간복잡도에서 무조건 문제가 생긴다.

문제를 다시 보니 DP 중 메모이제이션을 활용해 풀면 해결될 것 같다는 생각을 했고, 내가 생각한 알고리즘대로 풀어보니 답이 나왔다.

알고리즘

알고리즘 : DP (메모이제이션)

1. 위에서 아래로 내려간다 1번 인덱스부터 n번 인덱스까지
2. 0번 인덱스부터 i 인덱스까지 돌면서 값 업데이트
3. 가장 좌측이랑 우측이라면 각각 한번의 연산만 함
4. 모든 값을 업데이트한 뒤, 제일 바닥에서 값이 제일 큰걸 answer에 둔다

최종 코드

class Solution {
    int[][] triangle;
    
    public int solution(int[][] triangle) {
        int answer = 0;
        this.triangle = triangle;
        // 1. 위에서 아래로 내려간다 1번 인덱스부터 n번 인덱스까지
        int start = triangle[0][0];
        int len = triangle.length;
        
        for (int i = 1; i < len; i++) {
            // 2. 0번 인덱스부터 i 인덱스까지 돌면서 값 업데이트
            for (int j = 0; j <= i; j++) {
                // 3. 누적합 계산
                triangle[i][j] = memoization(i, j);
            }
        }
        
        // 4. 모든 값을 업데이트한 뒤, 제일 바닥에서 값이 제일 큰걸 answer에 둔다
        for (int i = 0; i < len; i++) {
            answer = Math.max(answer, triangle[len-1][i]);
        }
        
        return answer;
    }
    
    // h : 높이, w : 너비
    public int memoization(int h, int w) {
        int res = triangle[h][w];
        // 3-1. 가장 좌측 한번의 연산만 함
        if (w == 0) {
            res += triangle[h-1][0];
        }
        // 3-2. 우측이라면 한번의 연산만 함
        else if (h == w) {
            res += triangle[h-1][w-1];
        }
        // 3-3. 위의 두 경우가 아니라면 두 부모의 값 중 큰 것과 합한다.
        else {
            int num = Math.max(triangle[h-1][w-1], triangle[h-1][w]);
            res += num;
        }
        return res;
    }
}

깨달은 점

• DP(메모이제이션)을 개념으로만 알고 있었는데, 실제 문제를 만나고, 손으로 풀어보니 감을 잡았다.
• 이번 문제는 손으로 푼 풀이를 그대로 코드로 옮기는데 큰 어려움 없이 풀렸다.
  (나... 재능있나...?)
• 처음 문제를 볼 때, 알고리즘이 떠오르지 않으면 제약조건을 먼저 보자!!