프로그래머스 : 땅따먹기 Java

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

프로그래머스

 

틀린 풀이

class Solution {
	static int dontStep = -1;
	
	static int solution(int[][] land) {
		int answer = 0;
		
		for(int i=0; i<land.length; i++) {
			int max = maxStep(land[i]);
			answer += max;
			System.out.println("max : " + max);
		}
		return answer;
	}

	private static int maxStep(int[] arr) {
		int max = -1;
		int idx = -1;
		// 처음 시작인 경우
		if(dontStep == -1) {
			for(int i=0; i<arr.length; i++) {
				if(arr[i]>max) {
					max = arr[i];
					idx = i;
				}
			}
		} 
		// 처음 시작이 아닌 경우
		else {
			for(int i=0; i<arr.length; i++) {
				if(i != dontStep && arr[i]>max) {
					max = arr[i];
					idx = i;
				}
			}
		}
		dontStep = idx;
		return max;
	}
}

 

올바른 풀이

import java.util.Arrays;

class Solution {
	public static void main(String[] args) {
		int[][] arr = {{1,2,3,5},{5,6,7,8},{4,3,2,1}};
		System.out.println(solution(arr));
	}
	
	static int solution(int[][] land) {
		for(int i=1; i<land.length; i++) {
			land[i][0] += Math.max(Math.max(land[i-1][1], land[i-1][2]), land[i-1][3]);
			land[i][1] += Math.max(Math.max(land[i-1][0], land[i-1][2]), land[i-1][3]);
			land[i][2] += Math.max(Math.max(land[i-1][1], land[i-1][0]), land[i-1][3]);
			land[i][3] += Math.max(Math.max(land[i-1][1], land[i-1][2]), land[i-1][0]);
		}
		
		int[] answerArr = land[land.length-1];
		Arrays.sort(answerArr);
		
		int answer = answerArr[answerArr.length-1];
		return answer;
	}
}

 

처음 배열부터 큰수를 찾아서 간다면 뒤에 반전이 있을 수 있는 경우를 무시하는것이 된다.

그렇다고 모든 경우를 따지기엔 효율성 문제가 생긴다.

 

불가능한 열을 제외한 윗줄의 가장 큰 수를 더해준다.

마지막 행까지 반복해 마지막 행의 가장 큰 수로 답을 도출 할 수 있다.