자바(JAVA) - 땅따먹기(Programmers : 12913)

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

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

DP(동적 계획법)을 이용하여 풀 수 있었던 문제.
처음엔 정렬 문제일거라 생각했으나,,

각 행의 열이 다른 값들 중, 가장 큰 값을 다음 행에 더해나가며 정답을 구할 수 있었다.

 

실행 순서는 다음과 같다 :

    1. input 첫번째 행부터 마지막 행까지 확인하며,

    2. 다음 행의 c열에 현재 c 행이 아닌 3개의 값 중, 가장 큰 값을 더해줌

    3. 마지막 행에서 가장 큰 값 반환

 

 

<코드>

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