[프로그래머스] 2️⃣ 땅따먹기 (JAVA)

🔗 문제 링크

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

 

---

 

📍 문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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 이하의 자연수

입출력 예

land answer

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

16

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

---

😞 실패 풀이 → 단순히 큰 값만 생각함 (완탐으로 해도 시간초과)

import java.util.*;

/*
  --- for문 ---
   1. 1행부터는 가장 큰 값을 선정 (Arrays.sort())
        그러나, 이전에 선택한 열과 같을 경우 두 번째로 큰 값이 있는 열 선택 
        -> 선택한 열 갱신,  총 합에 더하기 

*/

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int nowColumn = -1;
        int preColumn = -1;
        
        List<Integer> list = new ArrayList<>();
        
    
        for (int[] arr : land){
            for (int i : arr){
                list.add(i);
            }
            // 배열 오름차순으로 정렬
            Arrays.sort(arr);
            
            // 현재 가장 큰 값이 있는 열의 인덱스 반환
            nowColumn = list.indexOf(arr[arr.length-1]);
            
            if (nowColumn == preColumn){
                // 그 다음으로 큰 값이 있는 인덱스 선택
                nowColumn = list.indexOf(arr[arr.length-2]);
                
                answer+= arr[arr.length-2];
                preColumn = list.indexOf(arr[arr.length-2]);
                
            } else {
                answer += arr[arr.length-1];
                preColumn = list.indexOf(arr[arr.length-1]);  
            }
            
            list.clear();
            
        }

        return answer;
    }
}

 

 

📍 DP를 활용한 풀이

 

1. 0번째 행은 이전 행의 열들을 신경 쓸 필요 없기에 dp에 바로 넣어준다.

2. 1번째 행부터 이전 행에서 선택한 열을 선택하지 않게 최댓값을 더하여 dp 배열에 넣어준다

3. 끝까지 반복한 후, 마지막 행에서 최댓값을 구한다.

 

import java.util.*;

/*
    - dp를 사용해서 가장 최댓값을 구함 : Math.max()
        
*/

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int SIZE = land.length;
        int dp [][] = new int [SIZE][4];
        
        //첫 행은 이전 열을 신경 쓸 필요가 없으므로 그냥 넣어줌.
        for (int i = 0; i < 4; i++){
            dp[0][i] = land[0][i];
        }
        
        for (int i = 1; i < SIZE; i++){
            // 이전 행에서 0번쨰 열을 선택했다면, 0번째 열을 빼고 이전 열들 계산
            dp[i][0] = land[i][0] + Math.max(dp[i-1][1], Math.max(dp[i-1][2], dp[i-1][3]));
            // 이전 행에서 1번쨰 열을 선택했다면, 0번째 열을 빼고 이전 열들 계산
            dp[i][1] = land[i][1] + Math.max(dp[i-1][0], Math.max(dp[i-1][2], dp[i-1][3]));
            // 이전 행에서 2번쨰 열을 선택했다면, 2번째 열을 빼고  이전 열들 계산
            dp[i][2] = land[i][2] + Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][3]));
            // 이전 행에서 3번쨰 열을 선택했다면, 3번째 열을 빼고 이전 열들 계산
            dp[i][3] = land[i][3] + Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][2]));
            
        }
        
        answer = Math.max(dp[SIZE-1][0], Math.max(dp[SIZE-1][1],Math.max(dp[SIZE-1][2], dp[SIZE-1][3])));

        return answer;
    }
}

---