<Algorithm> 216. 땅따먹기(Programmers)

 

1. 땅따먹기(Programmers)

   사용 알고리즘 :  DP

• 문제를 제대로 읽지 않아서 열이 최대 100,000 인줄알고 아무리 생각해도 3중 for문이 나오는데 ... 라는 착각을 했다.....
  
• 그래서 궁금증을 가지고 해설을 봤는데 3중for문이여서 말이되나 싶었는데 다시 읽어보니 열의 개수는 고정 4개 였다..

문제에 대한 접근&생각

1. 임의의 점을 설정 -> 역으로 탐색해서 해당위치의 최댓값을 구함 -> 자기열을 제외한 아래열의 최댓값을 더한다. 

코드 

 

class Solution {
    int solution(int[][] land) {
        int n = land.length;
        int[][] dp= new int[n+1][4];
        /***************************
         * DP를 활용하여 거꾸로 임의의 점이
         * 최대값이 될 수 있는 경우를 생각한다.
         ***************************/ 
        for(int i = n-1; i >= 0; i--) {
             for(int j = 0; j < 4; j++) {
                 int max = 0;
                 for(int u = 0; u < 4; u++) {
                     if(j!=u) max = Math.max(dp[i+1][u], max);
                 }
                 dp[i][j] = max+land[i][j]; 
                 // (i,j)를 선택했을때 최대치
            }
        }
        int max = Arrays.stream(dp[0]).max().getAsInt();
        return max;
    }
}

 

 

참고 & 출처  

https://programmers.co.kr/learn/courses/18/lessons/846