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

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

코딩테스트 연습 - 땅따먹기 | 프로그래머스

 

 

풀이

DP문제다. 어떻게 풀지 고민하다가 각 열마다 가장 큰 값을 찾고, 동일한 열이 아닐시 더해주는 식으로 생각을 했다... 결국 너무 복잡해지고 풀지못해 찾아보니 DP를 이용하면 쉽게 해결 할 수 있다.

DP란?

 

 

현재 행에서 밟을 열은 전의 열과 동일하게 밟을 수 없다.

1 2 3 5

5 6 7 8

위와 같이있을때, 첫번째 행에서 5를 밟으면 두번째 행에선 8을 밟을 수 없다.

 

각 행의 열마다 이전까지의 최댓값을 구해가는 식으로 푼다.

i번째 행의 값들에 i-1번째까지 행들의 값들의 최댓값을 구해가는 식이다.

두번째 행(5, 6, 7, 8)부터 이전 행의 최댓값들의 합을 더한다.

 

land[2][0] 에 올수 있는 최댓값은

land[2][0] + land[1][1] = 7

land[2][0] + land[1][2] = 8

land[2][0] + land[1][3] = 10

위에 세 값중 가장 큰 값인 10이다.

 

land[2][1] 에 올수 있는 최댓값은

land[2][1] + land[1][0] = 7

land[2][1] + land[1][2] = 9

land[2][1] + land[1][3] = 11

위에 세 값중 가장 큰값인 11이다.

 

land[2][2] 에 올수 있는 최댓값은

land[2][2] + land[1][0] = 8

land[2][2] + land[1][1] = 9

land[2][2] + land[1][3] = 12

위에 세 값중 가장 큰값인 12이다.

 

land[2][3] 에 올수 있는 최댓값은

land[2][3] + land[1][0] = 9

land[2][3] + land[1][1] = 10

land[2][3] + land[1][2] = 11

위에 세 값중 가장 큰값인 11이다.

 

따라서 위와 같이 된다.

아래로도 계속 똑같은 작업을 행하면 된다.

모든 작업이 끝나면, 0, 1, 2, 3 번째 열 중 가장 큰값을 고르면 된다.

 

PS. 각 행별로 정렬을 하고, 가장 마지막 행의 3번째 값을 출력해도 정답이다.

 

import java.util.*;

class Solution {
	public static int solution(int[][] land) {
		
		for(int i=1; i<land.length; i++) {
			land[i][0] += Math.max(land[i-1][1], Math.max(land[i-1][2], land[i-1][3]));
			land[i][1] += Math.max(land[i-1][0], Math.max(land[i-1][2], land[i-1][3]));
			land[i][2] += Math.max(land[i-1][1], Math.max(land[i-1][0], land[i-1][3]));
			land[i][3] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][2]));
		}
        
        for(int i=0; i<land.length; i++){
            Arrays.sort(land[i]);
        }
        return land[land.length-1][3];
		//return Math.max(land[land.length-1][0], Math.max(land[land.length-1][1], Math.max(land[land.length-1][2], land[land.length-1][3])));
	}
}