[ 프로그래머스 ] 땅따먹기 ( 자바 )

[ 프로그래머스 ] 땅따먹기 ( java )

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

 

 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/12913

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

 

핵심 

오류

1 현재 최대 값을 고르면? 

  다음 줄 같은 열에 가장 큰 100000 수가 있다면 틀린 선택이 됨. 

2 그럼 가장 첫 번째, 두 번째로 큰 점수만 유지하며 행을 검색하는건? 

   만약 한 행의 모든 열이 같은 값이면 어떤 것이 옳은 것인지 알 수 없다. 

3 그럼 모든 경우를 일일히 해보는데, 중복을 제거하자! => DP 

 

모든 경우 비교

최대 점수를 가지는 루트가 있다. 마지막 행에서 그 루트는 0 ~ 3 번째 중 하나를 선택하게 된다. 

어떤 것이 루트에 포함되는지 모르기 때문에, 0 ~ 3 번째 모든 경우를 고려해본다. 

올라갈 때는, 바로 위에 행 기준으로 아래에서 최대를 선택한다. ( 같은 열 제외 )

하지만, 모든 선택지를 일일히 저장할 수 없다. 시간초과 

=> 최대인 경우만 저장한다. 

 

DP ( BOTTOM-UP)

max[i] i는 0 ~ 3, max[i]는 i 열에서의 최대 점수 

 

위 단계를 거치면, max = [ 8, 10, 11, 12 ] 가 저장된다. 

이렇게 쭉 올라가면 된다.

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

 

코드

class Solution {
	int solution(int[][] land) {
		int len = land.length-1;
		int i0, i1, i2, i3;
		int[] max = { land[len][0],land[len][1], land[len][2], land[len][3] };
    
		for(int i = land.length-2; i >=0 ; i--) {
			i0 = maxVal(max[1], max[2], max[3]) + land[i][0];
			i1 = maxVal(max[0], max[2], max[3]) + land[i][1];
			i2 = maxVal(max[1], max[0], max[3]) + land[i][2];
			i3 = maxVal(max[1], max[2], max[0]) + land[i][3];
			
			max[0] = i0;
			max[1] = i1;
			max[2] = i2;
			max[3] = i3;
		}
		
		int ans = 0;
		for(int i = 0 ; i < 4 ; i++) {
			if(ans < max[i]) {
				ans = max[i];
			}
		}

		return ans;
	}
	 
	static int maxVal(int a1, int a2, int a3) {
		return Math.max( Math.max(a1, a2), a3 );
	}
}