[알고리즘] 프로그래머스 땅따먹기 ( 레벨2 - DP)

프로그래머스 레벨2 문제 중 '땅따먹기'라는 문제입니다. DP 기본 문제입니다.

• 문제 출처 : 링크 
• DP
• 관련 문제 : 프로그래머스 '가장 큰 정사각형 찾기' 문제

---

풀이 포인트

• 완전 탐색으로 풀이를 시도하게 되면 시간 초과가 발생하는 문제였습니다.
• 그래서 각 단계별로 진행하는 과정에서 최대가 되는 값을 메모라이제이션 해야되는 문제였습니다.
• 1행의 경우는 이전 값이 없기에 그대로 메모라이제이션 됩니다.
• 2행 부터는 1행의 같은 열을 제외한 나머지 값들과 합을 구해보고, 그 합들 중 최대가 되는 값을 저장해야 됩니다.
• 가령 2행의 4열 값인 8을 보면 이전 행의 5와 합을 할 수 없기에 최대값은 11이 되는데, 메모라이제이션 배열을 보면 해당 값이 최대가 아닙니다.

class Solution {
    
    private int findMax(int val, int idx, int[] land){
        int res = 0;
        for(int i = 0; i < land.length; i++){
            if(idx == i) continue;
            res = Math.max( res, val + land[i] );
        }
        
        return res;
    }
    
    int solution(int[][] land) {
        
        int answer = 0;
        int[][] arr = new int[land.length][land[0].length];
        
        for(int i = 0 ; i < land.length; i ++) {
            for(int j = 0 ; j < land[0].length; j++){
                if(i == 0) arr[i][j] = land[i][j];
                else {
                    arr[i][j] = findMax(land[i][j], j, arr[i-1]);
                    answer = Math.max(answer, arr[i][j]);
                }
            }
        }

        return answer;
    }
}

 

연관문제

2차원 배열에서 DP를 활용하여 문제를 풀이하는 문제로는 프로그래머스 '가장 큰 정사각형 찾기'가 있습니다.