[프로그래머스] 땅따먹기 (JAVA)

1. 소요시간 : 5분
2. 문제 사이트 : 프로그래머스
3. 문제 수준 : 레벨 2
4. 문제 유형 : 다이나믹 프로그래밍
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12913
7. 푼 날짜 : 2023.05.17

1. 사용한 자료구조 & 알고리즘

DP를 사용했다.

2. 풀이과정

다이나믹 프로그래밍의 점화식을 유도해 내면 된다.
이 문제는 백준의 RGB거리 문제와 99% 똑같이 때문에
사실 그 문제를 풀었기 때문에 빨리 문제를 풀 수 있었다.

이번에 새로 도착한 땅은 , 전의 땅 중에서, 현재 행이 아닌 땅 3개를 고르고, 거기까지 도달한 최댓값을 찾는다. 그리고 그 최댓값에 현재 행의 땅의 점수를 더해주면 된다.

3. 소스코드

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

        return max;
    }
}

4. 결과

5. 회고

고민해서 문제를 풀었다기 보다는 그냥 알고 있는 지식이었다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212