2022년 05월 14일 프로그래머스 - 땅따먹기(다이나믹 프로그래밍, DP)

 

 

 

import java.util.*;

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        
        //열의 길이 column - 3
        System.out.println(land.length);
        
        //행의 크기 row - 4
        System.out.println(land[0].length);

        
        //MAX 값 구하기
        for(int i=1; i<land.length; i++)
        {
            //같은 열을 못찾으니 그걸 제외하고 Math.max로 최댓값을 탐색하여 누적해 더해줌
            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]));
        }

        //Arrays.sort로 함수 정렬 - 2차원 배열은 정렬이 안되기에 번지수를 지정해주어야 함
        Arrays.sort(land[land.length-1]);
        
        //가장 큰 값이 맨 뒤로 가 있음
        answer = land[land.length-1][3];
        
        return answer;
    }
}

 

 

※ 참고자료

https://velog.io/@peppermint100/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%95%85%EB%94%B0%EB%A8%B9%EA%B8%B0-in-Java

프로그래머스 땅따먹기 in Java