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

 

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

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

import java.util.Arrays;
class Solution {
	    int solution(int[][] land) {
	        int answer = 0;
	        
	        for(int i=1; i<land.length; i++) {
	        	for(int j=0; j<4; j++) {
	        		int num=land[i][j];
	        		for(int k=0;k<4; k++) {
	        			if(j==k) continue;
	        			land[i][j]=Math.max(land[i][j], num+land[i-1][k]);
	        		}
	        		
	        	}
	        }
	        return Arrays.stream(land[land.length-1]).max().getAsInt();
	    }
	}

소요시간 : 30분

 

처음에 문제를 봤을 때 완전탐색으로 하면 되겠다고 생각했는데

N이 100,000인것을 보고 안되겠다고 생각을 했고 어떻게 풀지 고민을 많이 했습니다!

 

그러다가 생각난것이 현재 행보다 한칸위의 행에서 최대값을 선택하는 방법이었습니다.

 

예를들어 

 

1 2 3 5

5 6 7 8

4 3 2 1

 

이 있다면 1번째 행은 그대로 갑니다. 그리고 2번째 행부터 자신의 바로 위의 행에서 최대값을 찾아서 더해줍니다.

하지만 자신의 바로 윗행은 스킵해줍니다. 이렇게 계산을 해보면

1   2   3  5

10 11 12 11

16 15 13 13

처럼 나옵니다. 이 때 마지막 행에서 가장큰 값을 반환해주면 끝입니다~