[프로그래머스] lv2. 땅따먹기 [#DP]

 

문제보고 Permutation 문제인 줄 알았는데,

전부 시간 초과 나서 당황했던 문제

알고 보니 DP 였다!!!

 

 

---

1. 출처

---

 

프로그래머스

 

• land라는 N*4 배열 각 칸에는 점수가 써져있음
• 이동 경로에 따라서 점수를 먹을 수 있음
• 연속으로 같은 열 진입 못함
• 가장 큰 점수를 얻을 수 있는 경로를 찾아 최대 점수를 출력하는 문제

 

---

2. 설계

---

 

 

순열의 시간복잡도는 O(n!)이다.

행은 최대 10만 줄 까지 나올 수 있다.

그니까 10만줄 * O(10만!)이 되어서 시간초과가 나온 것이다.

 

문제 대충 읽었을 때 10만줄? 1억 안남겠네~ 순열로 가자~ 했던게 패착요인이었다 ㅎㅎ

 

 

DP면 어떠한 규칙이 있을까 따져보기 위해 1줄씩 생각해봤다.

 

1행 : 1 2 3 5 만 있을 땐 각자 위치의 수가 최대의 점수가 나올 수 있는 경로이다.

2행 : 5 6 7 8 까지 있다면, 나의 윗 줄의 각 col별 최대 점수와 합했을 때 가장 큰 점수가 나오는 곳을 찾으면 된다.

3행 : 4 3 2 1 까지 해봐도 나의 윗 줄의 각 col별 최대 점수와 합했을 때 가장 큰 점수가 나오는 곳을 찾으면 된다.

 

단, 연속으로 같은 열을 갈 순 없으니 전줄에 같은 열이 나오면 pass한다.

 

그럼 결과 배열은 다음과 같이 나올 수 있다.

 

1	2	3	5	전 / 후	1	2	3	5
5	6	7	8		5+5 = 10	6+5 = 11	7+5 = 12	8+5 = 13
4	3	2	1		4+13 = 17	3+13 = 16	2+13 = 15	1+13 = 14

 

 

최종적으로는 계산된 마지막 행에서 가장 큰 값만 찾으면 된다.

정답은 16

 

 

---

3. 전체 코드

---

class Solution {
    
    int solution(int[][] land) {
        int row = land.length;
        int col = land[0].length;
        
        int[][] score = new int[row][col];
        score[0][0] = land[0][0];
        score[0][1] = land[0][1];
        score[0][2] = land[0][2];
        score[0][3] = land[0][3];
        
        for(int i=1; i<row; i++){
            for(int j=0; j<col; j++){
                for(int d=0; d<4; d++){
                    if(j==d) continue;
                    score[i][j] = Math.max(score[i][j], land[i][j]+score[i-1][d]);
                }
            }
        }
        
        int max = 0;
        for(int i=0; i<4; i++){
            max = Math.max(max, score[row-1][i]);
        }
        
        return max;
    }
}