Lv.2 : 땅따먹기

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 위에서부터 아래로 땅따먹기하며 점수를 최대한 크게 만든다.
• 연속된 열의 땅을 밟을 수는 없다.
• 점수의 최대값을 반환한다.

🔸 문제 풀이 🔸

• 직전 행의 값들 중 같은 열이 아닌 값들 중 최대값을 누적해 나간다.
• 마짐가 행의 값들 중 최대값을 반환한다.

---

🔸 코드 🔸

class Solution {
    int solution(int[][] land) {
        int[][] dp = new int[land.length][4];

        for (int i = 0; i < 4; i++) {
            dp[0][i] = land[0][i];
        }

        for (int i = 1; i < land.length; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    if (j != k) {
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][k]);
                    }
                }
                dp[i][j] += land[i][j];
            }
        }

        int answer = 0;
        for (int i = 0; i < 4; i++) {
            answer = Math.max(answer,dp[land.length-1][i]);
        }

        return answer;
    }
}

🔸 코드 해석 🔸

• 현재 인덱스의 최대값을 dp배열에 저장해가며 계산한다.
  • 직전 행의 값들 중 현재 행과 다른 열의 값 중 최대값을 저장한다.
• 계산을 마무리하고 dp배열의 마지막 행 값들 중 최대값을 반환한다.

 

---

🔸 end 🔸

• 단순 구현으로 막 풀이 한 느낌인데, 열의 길이가 4 정도 뿐이라 효율성 문제도 없었던 것 같다.
• 다른 풀이를 보니, 재귀메서드로 빼서 한 인덱스를 제외한 최대값을 반환하는 방식으로 풀이한 방법도 있었다.