[프로그래머스] LV.2 땅따먹기 (자바 java)

[프로그래머스] LV.2 땅따먹기 (자바 java)

 

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

 

2. 풀이

완전탐색으로 풀었지만 시간초과

dp로 이전 행에서의 최댓값을 해당 행에 더해주는 식으로 dp 값 업데이트하며 마지막에 비교하는 풀이

 

3. 코드

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