[ 프로그래머스 ] level 2 : 땅따먹기 ( 자바)

프로그래머스는 level2도 왜 이렇게 어려운지 모르겠다..흑흑

Programmers Lv.2 dp (동적계획법 : 메모이제이션) 문제 풀이이다.  java 를 기준으로 풀이를 작성 한다.

[ 문제 설명 ]  

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

landanswer

[[1,2,3,5],[5,6,7,8],[4,3,2,1]]

16

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

 

이 문제를 풀기 위해서 먼저 완전 탐색을 진행하였다. dfs로 순회하면서 풀어 보았는데 문제의 예시는 풀리는데, 제출을 누르자

바로 모두 시간초과가 발생하였다. 

어떻게 풀까 고민하던 중 프로그래머스 시간초과는 메모이제이션을 활용하면 된다라는 공식을 가지고 풀이를 도전하였다.

처음에는 최고 값과 index만 찾아가며 memoization을 시도하였지만.. 비교를 계속 아래 까지 해야한다는 문제가 발생하였고, 이를 해결하기 위해서는 

전체 값을 모두 memo에 집어넣는 방법을 생각하였다.

[ 알고리즘 ] 

memo[0] 에는 land[0]의 값을 모두 집어넣어 초기값을 설정해 준다. 각 칸을 선택하였을 경우를 넣는 것이다.

그 이후 memo[1]~memo[N-1] 에는 첫번째 칸을 선택했을 경우 값을 넣어준다. 

memo[i][0]  = land[i][0] 으로 이 값을 선택하였을 경우를 넣어주고, 

0이 아닌, memo[i-1]1,2,3,번쨰 값들을 비교해서 가장 큰 값을 memo[i][0] 에 더해준다.

자바는 이렇게 비교해서 가장 큰 함수 찾을 경우 반복문을 이용해야 해서 너무 번거롭다.. 

3개 중 가장 큰 값을 찾기 때문에 그냥 비교 연산자를 이용하여 max값을 구하였다. \

그리고 마지막 최고 값은 memo[N-1]의 값 중에 가장 큰 값을 answer에 넣어 return 해주면 된다. 

아래는 이를 코드로 구현한 것이다. 

아래는 텍스트 코드 

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int N = land.length;
        int [][] memo = new int[N][4];
        memo[0] = land[0];
        for(int i = 1; i<N;i++){
            memo[i][0] = land[i][0] + ((memo[i-1][1]>memo[i-1][2] && memo[i-1][1]>memo[i-1][3])? memo[i-1][1] : memo[i-1][2]>memo[i-1][3]?memo[i-1][2]:memo[i-1][3]);
            memo[i][1] = land[i][1] + ((memo[i-1][0]>memo[i-1][2] && memo[i-1][0]>memo[i-1][3])? memo[i-1][0] : memo[i-1][2]>memo[i-1][3]?memo[i-1][2]:memo[i-1][3]);
            memo[i][2] = land[i][2] + ((memo[i-1][0]>memo[i-1][1] && memo[i-1][0]>memo[i-1][3])? memo[i-1][0] : memo[i-1][1]>memo[i-1][3]?memo[i-1][1]:memo[i-1][3]);        
            memo[i][3] = land[i][3] + ((memo[i-1][0]>memo[i-1][1] && memo[i-1][0]>memo[i-1][2])? memo[i-1][0] : memo[i-1][1]>memo[i-1][2]?memo[i-1][1]:memo[i-1][2]);      
        }
        for(int i = 0; i<4 ; i++){
            answer = memo[N-1][i]>answer?memo[N-1][i]:answer;
        }
        return answer;
    }
}

비교 연산자를 이용해서 짰더니 너무 식이 길어지는 상황이 발생하였지만

해결이 되었으니 만족한다

아래는 채점 결과 이다. 

프로그래머스에서 시간초과가 나면 무조건 메모이제이션을 생각해 보도록 하자!