[프로그래머스][JAVA][Lv. 2] 땅따먹기

문제 설명

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

---

제한 사항

---

입출력 예

---

풀이

class Solution {
    int solution(int[][] land) {
        int answer = 0;

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

---

후기

처음에 DFS로 풀었다가 시간이 너무 오래 걸려서 다른 방법을 생각해 봤다. 그 결과 밑으로 갈수록 어차피 자신과 똑같은 인덱스 말고는 다 선택할 수 있으므로 그때그때 최선의 선택을 하는 그리디로 풀면 쉽게 풀 수 있다. 각 케이스에서 더할 수 있는 가장 큰 수를 계속 저장하면 된다.