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

 

 

 

문제 링크

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

프로그래머스

 

 

 

문제

1. 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있다. 

2. 1행부터 땅을 밟으며 한 행씩 내려올 때, 얻을 수 있는 점수의 최댓값을 return하라.
3. 단, 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있다.
4. 행의 개수 N은 100,000 이하의 자연수
5. 열의 개수는 4개이고, 땅(land)은 2차원 배열
6. 점수 : 100 이하의 자연수

 

 

 

문제 풀이

다이나믹프로그래밍을 이용하여 각 행별로 최고점을 계산하여 마지막 행까지 구한다.

1. 각 단계별 총합 점수를 계산할 int [][] result을 만들고, 1행은 기존의 값과 동일하게 넣어준다. 

2. 2행부터 N행까지 각 행에 들어갈 최대 총합 점수를 담아준다. 

3. N행의 모든 열의 점수들을 비교하여 최대 점수를 return 한다.

 

 

 

코드

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

 

 

 

실행결과