문제

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

---

입력

• 2차원 배열

---

출력

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값

---

풀이

제한조건

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

접근방법

DP
행의 최대 갯수가 10만, 열이 최대 4개 존재하므로, 모든 경우를 탐색하는것은 시간초과가 발생한다.

최소한으로 탐색하며, 시간을 줄일 방법을 찾아보자.
이전 행에서 A열을 밟았다면, 다음 행에서 A행을 못 밟는다는것에 초점을 두자!

arr[k] : 현재 k번째 열을 밟았을 때의 최댓값
prev[k] : 이전에 k열을 밟았을 때의 최댓값
i : i번째 행

arr[k] = prev[k]+land[i][k]

과 같은 수식으로 계산할 수 있다.

그럼 마지막에 4개의 계산된 값중 최댓값을 찾으면, 최대 10만번의 순회로 정답을 찾을 수 있다.

---

코드

class Solution {
    int solution(int[][] land) {
        int len = land.length;
        int[] dp = new int[4];
        
        for(int i = 0; i < len; ++i){
            int[] prev = dp.clone();
            dp[0] = Math.max(Math.max(prev[1], prev[2]), prev[3]) + land[i][0];
            dp[1] = Math.max(Math.max(prev[0], prev[2]), prev[3]) + land[i][1];
            dp[2] = Math.max(Math.max(prev[0], prev[1]), prev[3]) + land[i][2];
            dp[3] = Math.max(Math.max(prev[0], prev[1]), prev[2]) + land[i][3];
        }
        
        int answer = 0;
        for(int value : dp)
            answer = Math.max(answer, value);
        
        return answer;
    }
}