프로그래머스 - (Java)땅따먹기

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

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

1. 유형

동적프로그래밍

 

2. 로직

그림으로 이해

제한 조건을 잘 읽어보면 N이 100,000씩 되는걸 확인 가능하다

이러면, 부르트포스로는 4*3^(n-1)시간이 걸리고 시간초과로 실패가 뜰것이다.

제한조건을 잘 읽어보고 푸는 습관을 들이자

3. 코드

import java.util.*;
class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int height = land.length;
        int dp[][] = new int[height][4];
        int temp;
        for(int j=0; j<4; j++)
            dp[0][j] = land[0][j];
        for(int i=1; i<height; i++){
            for(int j=0; j<4; j++){
                temp=findMinNum(j, dp[i-1]);
                dp[i][j] = land[i][j]+temp;
            }
        }
        Arrays.sort(dp[height-1]);
        answer = dp[height-1][3];
        return answer;
    }
    static int findMinNum(int idx, int[] arr){
        int num = 0;
        for(int j=0; j<4; j++){
            if(j == idx) continue;
            num=Math.max(num, arr[j]);
        }
        return num;
    }
}
/*
로직
1. dp
2. 그 전에 행에서 최대값을 선택
*/