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

- 오늘의 학습 키워드 : DP

[문제 이름 :   정수 삼각형 (프로그래머스 DP, Lv 3) ]

문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/43105

 

내가 작성한 코드는 아래와 같다.

재귀와 메모리제이션을 이용하여 문제를 풀었다.
DP 관련 문제는 항상 위->아래, 아래->위로 갈 수 있는지 확인하고, 이에 대한 점화식을 세우는 게 중요한 것 같다.

public int solution(int[][] triangle) {
        int[][] memo = new int[triangle.length][triangle.length];
        return memorization(triangle, memo, 0, 0);
    }
    
    static int memorization(int[][] triangle, int[][] memo, int row, int col) {
        if(row == triangle.length - 1) {
            return triangle[row][col];
        }

        if(memo[row][col] != 0) {
            return memo[row][col];
        }

        int left = memorization(triangle, memo, row+1, col);
        int right = memorization(triangle, memo, row+1, col+1);
        
        memo[row][col] = triangle[row][col] + Math.max(left, right);
        return memo[row][col];
    }

[풀이 과정]

1. row가 삼각형의 마지막 행(triangle.length - 1)에 도달하면, 해당 위치의 값을 반환한다. 이는 더 이상 아래로 내려갈 수 없음을 의미한다.

2. memo[row][col]에 이미 계산된 값이 있는 경우, 해당 값을 바로 반환하여 불필요한 재계산을 방지한다.

3. left는 왼쪽 아래 경로로 이동한 결과를 저장하고, right는 오른쪽 아래 경로로 이동한 결과를 저장한다.

4. memo[row][col]의 값을 반환하여 재귀 호출로 값을 전달한다.

 

메모리제이션을 말고도, 아래와 같은 점화식을 유도하여 풀이할 수도 있었다.

최대합을 구하는 규칙(점화식)을 유도하여, 정답을 구하는 방식이다.

    public int solution(int[][] triangle) {
        int len = triangle.length;
        
        for(int i=1; i<len; i++) {
            for(int j=0; j<=i; j++) {
                // 제일 왼쪽
                if(j==0) {
                    triangle[i][j] += triangle[i-1][j];
                } else if (j==i) {
                    // 제일 오른쪽
                    triangle[i][j] += triangle[i-1][j-1];
                } else {
                    // 그 사이
                    triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
                }
            }
        }
        
        int answer = 0;
        Arrays.sort(triangle[len-1]);
        int lastLen = triangle[len-1].length;
        return triangle[len-1][lastLen-1];
    }

풀이 시간 : 30분

 

이전에 백준에서 동일한 문제를 풀어본 적이 있어, 비교적 빠르게 문제풀이 방법을 떠올릴 수 있었다.

백준 문제 링크 : https://www.acmicpc.net/problem/1932

내일은 순열, 조합 코딩 테스트 문제에 대해 풀어보고자 한다.