[ 알고리즘 ] 코딩 - Programmers - 땅따먹기.java

---

문제 링크

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

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

---

* 프로그래머스 - Level 2 - (자바) 땅따먹기 - DP

 

* 한 행 씩 내려가며 숫자 하나를 선택

* 같은 열을 연속으로 선택 할 수 없음

제한 사항

 

---

< 로직 >

* 행의 개수가 10만개다! DFS로 푸는 순간 시간 초과가 걸릴 것이다! 하고 압박을 준다.

* 큰 문제를 작은 문제로 나누어 데이터를 재사용하는 방법인 DP를 이용해서 풀고자 했다.

* 바로 아래 선택과 자신의 선택만 다르면 무엇을 선택하든 상관이 없다!

* save_sums = 선택해온 누적 합

* tmp = 변경되기 직전의 save_sums의 원래 값

* 가장 밑의 열부터 시작해서 tmp의 자신과 같은 인덱스는 제외

* 저장된 다른 누적 합(save_sums)과 현재 자신의 숫자를 더함 이 때 최대 값 저장

* 저장 한 최대값을 누적합 배열 중 현재 자신의 인덱스에  저장

* 위 과정을 반복 수행한다.

* 모든 과정이 끝나고 save_sums의 숫자중 가장 큰 수가 정답이다.

---

class Solution {
	    int solution(int[][] land) {
	    	int MAXLENGTH = 4;
	        int[] save_sums = new int[MAXLENGTH]; // 누적합 저장
	        int[] tmp = new int[MAXLENGTH]; // 누적 합 변경 하기 전 원본 저장
	        int max = land.length-1;
	        
	        for(int j = 0; j < 4; j++) {
	        	save_sums[j] = land[max][j]; // 가장 밑에서 부터 시작
        	}
	        
	        for(int i = max-1; i >= 0; i--) {
	        	for(int j = 0; j < MAXLENGTH; j++) {
	        		tmp[j] = save_sums[j]; // 원본 저장
	        	}
	        	
	        	for(int j = 0; j < MAXLENGTH; j++) {
	        		int resMax = 0;
	        		for(int k = 0; k < MAXLENGTH; k++) {
	        			if(j == k) continue;
	        			int sum = tmp[k] + land[i][j];
	        			// 골랐을 때 최대 값 저장
	        			resMax = sum > resMax ? sum : resMax;
	        		}
	        		// 최대 값만 가지고 올라간다
	        		save_sums[j] = resMax;
	        	}
	        }
	        
	        int answer = 0;
	        // 누적하며 저장 한 값 중 가장 큰 값이 최대값
	        for(int i = 0; i < MAXLENGTH; i++) {
	        	answer = Math.max(answer, save_sums[i]);
	        }
	        return answer;
	    }
	}