#프로그래머스_땅따먹기 - Java 자바

#유형 : 시뮬레이션, 탐색

#난이도 : LV2

# 맨 처음에는 문제를 제대로 읽지않고 접근하여 인접한 행으로만 이동 가능한 줄 알았다...

dfs 같은 탐색으로 접근하려다가 시간복잡도가 너무 안좋아서 한 행마다 Math.max로 접근하여 해결하였다.

land[i][1]은 land[i-1][0], land[i-1][2], land[i-1][3]중 가장 큰값과 더하면 된다.

이것을 N의 배열길이 - 1 만큼 반복해주면 된다.

class Solution {
    int solution(int[][] land) {
        int answer = 0;
 
        for(int i=0; i<land.length-1; i++){
            land[i+1][0] += Math.max(Math.max(land[i][1], land[i][2]), land[i][3]);
            land[i+1][1] += Math.max(Math.max(land[i][0], land[i][2]), land[i][3]);
            land[i+1][2] += Math.max(Math.max(land[i][0], land[i][1]), land[i][3]);
            land[i+1][3] += Math.max(Math.max(land[i][0], land[i][1]), land[i][2]);
        }
        
        for(int i=0; i<4; i++){
            answer = Math.max(answer, land[land.length-1][i]);
        }
 
        return answer;
    }
}