[프로그래머스] level2. 땅따먹기 (자바 JAVA)

[ 문제 ]  [프로그래머스] level2. 땅따먹기 (자바 JAVA)

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12913

코딩테스트 연습 - 땅따먹기

---

# 접근 방법 및 풀이 

 

• 일단 완탐을 해야된다고 생각했다. 해당 행에 어떤 열을 선택해서 다 더했을때 값이 최대이므로 다짜고짜 dfs짰다..^^
• 당연히 시간초과 나서 다 틀렸다. 왜 나는 자꾸 시간범위를 생각해보지 않을까?
• n이 최대 10만이기 때문에 시간 초과가 난다.
• 첫행에서 4개중에 1개, 그이후로 윗 행에서 뽑은 열을 제외하기때문에 3개씩 뽑을 수 있다.
• 따라서 시간복잡도는 최대 4*3^n-1이다. 여기 n에 10만이 들어간다면,, 당연히 최악이다.
• 뭔가 DP 느낌이 와서.. DP공포증으로 인터넷 찾아봤다.
• 생각보다 쉽게 이해할 수 있었다! DP라고 무작정 겁먹지말고 개념정리를 좀 확실히 한 후에 점화식 세우는 부분을 고려해야겠다.
• 일단 쉽게 생각하면 i번째 행에서 열이 선택되었을때 i-1번째 행 중 선택된 열을 제외한 나머지들 중 최대값을 구해서 더하는 형태다. 
• 예시로,  초기 land[][]의 상태다.

• idx	0	1	2	3
  0	1	2	3	5
  1	5	6	7	8
  2	4	3	2	1

• 우리가 눈 여겨볼 곳은 0번째 행이 아닌 1번째 행이다. 1번째 행의 각 land[1][0], land[1][1], land[1][2], land[1][3]에 값을 갱신해줄 것이다.
• 먼저, land[1][0]은 0번째 열을 선택했다고 생각해보자. 1번째 행의 윗 행이 0번째 행에서
• 0번째 열을 제외한 land[0][1], land[0][2], land[0][3] 중에 값을 고를 수 있고, 최대값은 5가된다.
• 기존 land[1][0] 값인 5에 5를 더한 10으로 land[1][0]의 값을 갱신시켜준다.

• idx	0	1	2	3
  0	1	2	3	5
  1	5 + 5 = 10	6 + 5 = 11	7 + 5 = 12	8 + 3 = 11
  2	4	3	2	1

•  다음과 같이 파란글씨(기존값)에서 최대값을 더한 굵은 글씨로 갱신된다.
• 이 방식으로 n-1행까지 값을 갱신해주면

• idx	0	1	2	3
  0	1	2	3	5
  1	10	11	12	11
  2	12+4 = 16	12+3 =12	11+2 = 13	12+1 = 13

• 마지막행에 갱신된 값 중 최대값을 뽑으면 정답이 된다. 따라서 답은 16!
• 자세한건 코드참조

# 주의할 점 

 

• 완탐할 경우 시간초과날지 꼭 확인해보기! 무작정 완탐으로 덤벼들지말기.

 

JAVA 코드

완전탐색 코드 -> 시간초과남

class Solution {
    static boolean visit[][];
    static int N, ans = 0;
    int solution(int[][] land) {
        visit = new boolean[land.length][4];
        N = land.length;
        dfs(0, 0, land);
        int answer = ans;
        return answer;
    }
    public static void dfs (int r, int sum, int[][] land){
        if(r == N){
            ans = Math.max(ans, sum);
            return;
        }
        for(int j = 0; j < 4; j++){
            if(!visit[r][j]){
                sum += land[r][j];
                if(r < N-1)
                    visit[r+1][j] = true;
                dfs(r+1, sum, land);
                if(r < N-1)
                    visit[r+1][j] = false;
                sum -= land[r][j];
            }
        }
    }
}

DP코드 -> 통과

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        for(int i = 1 ; i< land.length; i++){
            land[i][0] += Math.max(land[i-1][1],Math.max(land[i-1][2],land[i-1][3]));
            land[i][1] += Math.max(land[i-1][0],Math.max(land[i-1][2],land[i-1][3]));
            land[i][2] += Math.max(land[i-1][0],Math.max(land[i-1][1],land[i-1][3]));
            land[i][3] += Math.max(land[i-1][0],Math.max(land[i-1][1],land[i-1][2]));
        }
        for(int i = 0; i < 4; i++){
            answer = Math.max(answer,land[land.length-1][i]);
        }
        return answer;
    }
}

 

 

REVIEW