programmers 땅따먹기

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

코딩테스트 연습 - 땅따먹기

 

 

문제 분석

- dp를 활용하여 문제를 푼다. 각 행에 직전 행에서 본인의 열을 제외한 나머지 3개 중 가장 큰 값을 더하여 계산한다.

- 마지막 행에서 가장 큰 변수를 구하여 정답을 반환한다.

 

 

문제 풀이

1. for문을 통해서 직전 행에서 가장 큰 수를 더하여 처리한다.

2. 마지막 행의 배열을 정렬하여 가장 큰 변수를 반환한다.

import java.util.*;

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

 

 

https://github.com/SOEUN2/Algorithm