[dp] 프로그래머스 땅따먹기(실패분석- 시간부족)

접근

https://school.programmers.co.kr/learn/courses/30/lessons/12913

이 문제는 메모제이션을 이용한 문제입니다.

처음에 DFS를 이용해서 풀었으나 사실 DFS와 완전탐색의 방법 차이는 크게 없었습니다.
backtracking을 이용한 방법도 아니고 뭔가 DFS를 덜 진행할 방법이 없었기 때문입니다.

따라서 DFS로 풀면 시간초과가 발생했고
메모제이션을 통한 아이디어를 생각해냈지만
30분 이내 풀지 못해 실패했습니다.

메모제이션을 이용한 방법은 아래와 같습니다.

1	2	3	5
5	6	7	8
4	3	2	1

초기

1	2	3	5
10	11	12	11
4	3	2	1

land[1]의 최대값은 그 이전에 존재하는 숫자 중에 가장 큰 수를 더한 값

1	2	3	5
10	11	12	11
16	15	13	13

land[2]의 최대값은 그 이전에 존재하는 숫자 중에 가장 큰 수를 더한 값

이런식으로 land 자체의 값을 메모제이션을 이용해서 갱신하는 것입니다.

풀이(DP)

import java.util.*;

class Solution {
    
    int solution(int[][] land) {
         
        int target = land.length;
        
        int index=1;
        while(index<target){
         for(int i=0;i<4;i++){
            int max = Integer.MIN_VALUE;
            for(int j=0;j<4;j++){
                 // 같은 열이면 continue;
                if(j==i) continue;
                // 같은 열이 아니라면 가장 큰 수 구하기
                if(max<land[index-1][j]) max=land[index-1][j] ;
            }
            // 현재 값과 그 이전 행의 가장 큰수를 더한 값을 land에 갱신
            land[index][i]+=max;
          }
          
         index++;
        }
        
        // 결국 가장 마지막 행에는 만들 수 있는 가장 큰 수가 누적되어 있음
        // 그 중에서 가장 큰 수를 구하기
        int max = Integer.MIN_VALUE;
        for(int i=0;i<4;i++){
             max = max<land[target-1][i]?land[target-1][i]:max;
        }
        
        return max;
              
    }
}

풀이(DFS-시간초과)

import java.util.*;

class Solution {

    

    static int max = Integer.MIN_VALUE;
    static int target=0;
    int solution(int[][] land) {
         
        //행의 길이
        target = land.length;
        
        //level1로 dfs 시작
        for(int i=0;i<4;i++)
                dfs(land,land[0][i],0,i);        
        
        return max;
           
    }
     
    static void dfs(int[][] land,int sum, int row, int col){
        if(row==target-1){
            if(max<sum) max=sum;
        }else{
            for(int i=0;i<4;i++){
                //같은 열일 경우 continue
                if(i==col) continue;
                int newRow = row+1;
                int newSum = sum+land[newRow][i];
                //dfs에 넣기
                dfs(land,newSum,newRow,i);
            }            
        }
    }
}