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

문제

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

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

풀이

정수 삼각형과 유사한 문제이다. 

land와 동일 사이즈의 배열을 생성하여 

행과 열을 순회하면서, 해당 index에서 가질 수 있는 최대 점수를 저장해나간다. 

마지막 행의 최대 값이 답이 된다.

2021.11.08 - [Problem Solving/BOJ] - [BOJ 1932] 정수 삼각형 (Java)

[BOJ 1932] 정수 삼각형 (Java)

 

소스코드

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

        return answer;
    }
}