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

문제 출처 - Programmers

문제는 여기

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

---

[풀이]

1. 첫 번째 행은 고정이므로 다음 행부터 탐색을 한다.

2. 총 4개의 열이므로 4번 반복을 한다.

3. 다음 행에서 어떤 열을 선택해야 할지 정해야 하므로 4번 반복한다.

4. 3. 에서 똑같은 열을 선택하면 안되므로 제외해준다.

5. 4. 에서 제외하고 가장 큰 숫자를 골라 합해준다.

6. 이 과정을 모든 행을 반복한다.

7. 마지막 행에서 가장 큰 값을 출력한다.

[접근]

1. dp처럼 위에서부터 값을 체크해가면서 마지막에 가장 큰 값을 출력하면 되겠다고 생각하였다.

[코드]

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        
        // 맨 아래까지 탐색
        for (int i = 1; i < land.length; i++) {
            // 열의 개수 4개
            for (int j = 0; j < 4; j++) {
                // 최고 값을 구하기 위한 변수
                int max = 0;
                
                for (int k = 0; k < 4; k++) {
                    // 이전 열과 현재열이 같으면 안됨
                    if (j == k)
                        continue;
                    // 가장 큰 수 구하기
                    max = Math.max(land[i - 1][k] , max);
                }
                // 가장 큰 수 더해주기
                land[i][j] += max;
            }
        }

        // 마지막 행의 가장 큰 값이 최고점
        answer = Math.max(land[land.length - 1][0], Math.max(land[land.length - 1][1], Math.max(land[land.length - 1][2], land[land.length - 1][3])));

        return answer;
    }
}