[Algorithm/Java][프로그래머스] 땅따먹기

[프로그래머스] 땅따먹기

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

문제 접근

처음에 접근할 때 dfs로 풀어야 될까? dp로 풀어야 될까? 고민이 되었는데 dfs로 코드 짜려고 하니까 그냥 바로 막혀서 dp로 생각해봤다.
일단 접근 방식은 현재 내가 밟은 땅과 같은 열을 제외하고 바로 전 행에서 최고점수를 가진 곳을 밟아야 최고 점수를 유지하면서 땅을 밟아갈수 있다.
그래서 dp배열에 그 위치에 해당하는 최고점수를 저장하고, 마지막 행중에서 최고 점수가 최종 답이 된다.

Code

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int[][] dp = new int[land.length][4];  // 각 열마다 최고점수를 기록할 배열이다.
        dp[0] = land[0]; // 첫번째 행은 그대로가 최고 점수이다.
        for(int i = 1; i<land.length; i++){
            for(int j = 0; j<4; j++){
                for(int k = 0; k<4; k++){
                    if(k==j) continue;
                    // 이전 행에서 현재 열을 제외하고 가장 큰 값을 찾는다.
                    dp[i][j] = Math.max(dp[i-1][k]+land[i][j], dp[i][j]);
                }
            }
        }
        // 마지막 행에서 가장 점수가 높은 열을 찾는다.
        for(int score: dp[land.length-1]){
            answer = Math.max(score,answer);
        }
        return answer;
    }
}

어려웠던 점 / 배운 점 / 느낀 점

프로그래머스 level 2 단계인데 잘 풀려서 기분이 좋았다. 한방에 정답이다👍