Programmers - 땅따먹기

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

---

문제

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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 하면 됩니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

land : [[1,2,3,5],[5,6,7,8],[4,3,2,1]]

answer : 16

---

 

오호라 첫줄부터 최대값을 구한 뒤 한 줄 씩 내려오면서  앞줄과 겹치지 않는 칸을 제외한 가장 큰 값을 더해 나가면 되겠다 생각했다.

 

import java.util.*;
class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int[] stepped = new int[land.length];
        
       
        for(int i = 0 ; i < land.length ; i++){
            int score = 0;
            for(int j = 0 ; j < land[i].length ; j++){
                // System.out.println("looking : " + land[i][j]);
                if(i==0){
                   if(score < land[i][j]){
                        score = land[i][j];
                        stepped[i] = j;
                    } 
                }else{
                    if(score<land[i][j]){
                        if(stepped[i-1] != j){
                            score = land[i][j];
                            stepped[i] = j;
                        }
                    }
                }
                // System.out.println(Arrays.toString(stepped));

            }// end of j
            answer = answer + score;
            // System.out.println("--------score : " + score + "-------------");
        }//end of i
                // System.out.println("picked : " + Arrays.toString(stepped));

        return answer;
    }
}

 

테스트 케이스만 통화하고 제출 케이스는 다 틀린다.

 

다시 생각해 보니

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7| 10| 

이 상황에서 내 코드는 거침없이 5를 픽하지만 첫줄은 3을 선택하고 두번째 줄에서 10을 선택해야 한다.

 

모든 합의 경우를 다 구하여 최대값을 찾기엔 행의 개수가 100,000이하의 자연수로 너무 많다.

 

 

DP 로 풀어야 된다고 한다.

 

핵심은 첫줄을 기준으로 다음 줄의 최대값을 찾는게 아닌 뒷항목에서 첫항목을 더한 뒤 그 합의 최댓값을 찾는 것이다.

 

// [1, 2, 3, 5]
// [5, 6, 7, 8]
// [4, 3, 2, 1]

[5. 6. 7. 8] 에서부터 비교를 시작하여 앞 항목에서 본인과 같은 칸을 제외한 것들 중 최댓값을 자기자신과 더한다.
[5+MAX(2,3,5),6+MAX(1,3,5),7+MAX(1,2,5),8+MAX(1,2,3)]
[10,11,12,11] 이렇게 결과가 나오는데 마찬가지로 또 계산을 하면
[4, 3, 2, 1] 에 대해서
[4+MAX(11,12,11),3+MAX(10,12,11),2+MAX(10,11,11),1+MAX(10,11,12)]
[16,15,13,13] 로 최댓값은 16으로 답이 나온다.

 

import java.util.*;

class Solution {
	public static int solution(int[][] land) {
        // [1, 2, 3, 5]
        // [5, 6, 7, 8]
        // [4, 3, 2, 1]
        /*
        [5+MAX(2,3,5),6+MAX(1,3,5),7+MAX(1,2,5),8+MAX(1,2,3)]
        [10,11,12,11]
        [4, 3, 2, 1]
        [4+MAX(11,12,11),3+MAX(10,12,11),2+MAX(10,11,11),1+MAX(10,11,12)]
        [16,15,13,13]
        */
    
		for(int i=1; i<land.length; i++) {
			land[i][0] = land[i][0] +  Math.max(land[i-1][1], Math.max(land[i-1][2], land[i-1][3]));
			land[i][1] = land[i][1] +  Math.max(land[i-1][0], Math.max(land[i-1][2], land[i-1][3]));
			land[i][2] = land[i][2] +  Math.max(land[i-1][1], Math.max(land[i-1][0], land[i-1][3]));
			land[i][3] = land[i][3] +  Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][2]));
            // System.out.println(Arrays.toString(land[i]));

		}
        
        Arrays.sort(land[land.length-1]);
        return land[land.length-1][3];

	}
}