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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12913
레벨 : Level 2
분류 : 연습문제

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

이 문제의 유형은 다이나믹 프로그래밍이다.

지나온 길의 점수를 합산하여 가장 큰 점수를 구하는 문제이다.

 

처음에는 첫 행부터 차례대로 큰 값을 찾고 지난 위치를 기억하여 지난 위치를 제외해 큰 값을 찾는 방식으로 구현하였으나 실패하였다.

 

다이나믹하지 못해 다른 사람의 풀이를 찾아 보았다.

첫 행에서 무조건 큰 값으로 시작하는것이 아닌 두번째 행부터 모든 열을 거쳤을때를 가정하여 가장 큰 값을 구하는 방식으로 구현하였다.

 

아래와 같이 풀이를 공유합니다.

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

        return answer;
    }
}