땅따먹기

유태형·2022년 2월 11일

코딩테스트 프로그래머스

프로그래머스 - Level 2

목록 보기

8/36

풀이

문제 분석

1행부터 이전 열을 제외한 최대값만 구하려하면 안될것 같다.

풀이

막혔던 점

2행에 8이 아니라 아주 큰 수면 1행부터 최대값을 고르며 진행 하는건 옳지 않다고 생각하여 최대값이 있는 행을 미리 구하고 위의 행들 아래 행들을 따로 구하려고 했다. 테스트 케이스는 통과했지만 예제는 전부 실패!

동적 프로그래밍

https://shanepark.tistory.com/183

현재의 값 + 이전의 최대 경로로 각 열을 계산해 나가는 방식

	for(int i=1; i<length; i++) { //첫째 행부터 마지막 행까지
            land[i][0] += max(land[i-1][1], land[i-1][2], land[i-1][3]); //0열
            land[i][1] += max(land[i-1][0], land[i-1][2], land[i-1][3]); //1열
            land[i][2] += max(land[i-1][1], land[i-1][3], land[i-1][0]); //2열
            land[i][3] += max(land[i-1][1], land[i-1][2], land[i-1][0]); //3열
        } //이전 최대 경로 + 현재 값

마지막 각 열은 최대 경로가 될 것이며 최대 값을 고르면 된다.

코드

class Solution {
     int solution(int[][] land) {
        final int length = land.length;
 
        for(int i=1; i<length; i++) {
            land[i][0] += max(land[i-1][1], land[i-1][2], land[i-1][3]);
            land[i][1] += max(land[i-1][0], land[i-1][2], land[i-1][3]);
            land[i][2] += max(land[i-1][1], land[i-1][3], land[i-1][0]);
            land[i][3] += max(land[i-1][1], land[i-1][2], land[i-1][0]);
        }
 
        return max(land[length-1]);
    }
 
    public int max(int a, int b, int c) {
        return Math.max(Math.max(a, b), c);
    }
 
    public int max(int[] arr) {
        int max = 0;
        for(int number : arr) {
            max = Math.max(max, number);
        }
        return max;
    }
}