Java 프로그래머스 땅따먹기

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

프로그래머스

문제 분류 : 코딩테스트 연습 > 연습문제 > 땅따먹기 

난이도 : 2

 

문제 접근 1 (테스트 케이스 전부 시간 초과) 

처음에는 큐를 활용한 완전 탐색을 사용하였다.

import java.util.*;

class Solution {
    static class node{
        int score; int before; int cur;
        public node (int score, int before, int cur){
            this.score = score; this.before = before; this.cur = cur;
        }
    }
    int solution(int[][] land) {
        int answer = 0;
        int check = land.length; 
        int max = 0;
        Queue<node> q = new LinkedList<>();
        for(int i = 0; i < 4; i++){
            max = Math.max(max, land[0][i]);
            q.add(new node(land[0][i], i, 0));
        }
        if(check == 1){
            return max;
        }  
        while(!q.isEmpty()){
            node node = q.poll();
            for(int i = 0; i < 4; i++){
                if(node.before == i) continue;
                if(node.cur + 1 == check - 1){
                    max = Math.max(max, node.score + land[node.cur + 1][i]);
                }
                else{
                    q.add(new node(node.score + land[node.cur + 1][i], i, node.cur + 1));
                }
            }
        }
        return max;
    }
}

행의 개수(N) : 100000이하의 자연수 

열의 개수는 4니까 시간 복잡도를 계산하면 O(4^10000) 이다. 완전 탐색으로는 시간초과가 당연하게 발생!

 

문제 접근 2 (정답 코드)

DP(다이나믹 프로그래밍)을 활용해서 풀었다.

class Solution {
     int solution(int[][] land) {
         int size = land.length;            // size = 행의 개수  
         int [][] DP = new int[size+1][4];
         for(int i = 1; i <= size; i++){
            for(int j = 0; j < 4; j++){
                int max = 0;
                for(int k = 0; k < 4; k++){
                    if(j == k) continue;    // 같은 열은 선택 x
                    max = Math.max(max, DP[i-1][k]);
                }
                DP[i][j] = max + land[i-1][j];
            }    
         }
         int answer = 0;
         for(int i = 0; i < 4; i++){
             answer = Math.max(answer, DP[size][i]);
         }
         return answer;
      }
}

 

시간복잡도는 N이 100000 * 4 * 4 니까 연산 횟수가1600000으로 무난하게 통과한다.