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

코드 힌트

1. 문제 이해 및 접근 방식:
   • 이 문제는 "땅따먹기"라는 게임을 기반으로 합니다. 각각의 행은 특정 턴에서 선택할 수 있는 네 개의 땅을 나타내고, 각 땅에는 점수가 부여됩니다. 같은 열의 땅은 연속해서 선택할 수 없습니다.
   • 목표는 마지막 행에 도달했을 때 얻을 수 있는 최대 점수를 계산하는 것입니다.
2. 동적 계획법을 활용한 점수 계산:
   • 각 행에서 가능한 최대 점수를 누적하는 방식으로 계산합니다.
   • land[i][j]에는 현재 위치까지의 최대 점수가 저장되며, 이전 행에서 같은 열을 제외한 최대 값을 더해나갑니다.
   • 즉, land[i][j]에는 i-1행에서 j열을 제외한 최대 점수가 더해집니다.
3. 이동 제한 처리:
   • 연속해서 같은 열을 선택할 수 없으므로, j열을 제외한 k열의 최대 점수를 선택해야 합니다. 이를 위해 내부 반복문에서 if (k != j) 조건을 사용합니다.
   • 이 조건을 통해 이전 행에서 선택할 수 있는 가장 큰 점수를 찾고, 현재 행의 점수에 누적시킵니다.
4. 최종 결과 계산:
   • 모든 행을 순회한 후, 마지막 행에서 얻을 수 있는 최대 점수를 반환합니다. 이는 마지막 행의 네 열 중 가장 큰 값을 선택하여 반환하는 방식으로 구현됩니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    int solution(int[][] land) {
        int result = 0;
        
        // 1번째 행부터 마지막 행까지 반복 (각 행에 대해 가능한 최대 점수를 계산)
        for (int i = 1; i < land.length; i++) {
            for (int j = 0; j < 4; j++) {
                int max = -1;
                
                // 연속해서 같은 열(j)로 갈 수 없으므로, 이전 행(i-1)에서 현재 열(j)을 제외한 가장 큰 값을 찾음
                for (int k = 0; k < 4; k++) {
                    if (k != j && land[i-1][k] > max) {
                        max = land[i-1][k];
                    }
                }
                
                // 현재 행(i)의 열(j)에 이전 행의 최대 값을 더하여 누적
                land[i][j] += max;
            }
        }
        
        // 마지막 행에서 가장 큰 값을 찾아 결과로 반환
        for (int i = 0; i < 4; i++) {
            result = Math.max(result, land[land.length-1][i]);
        }
        return result;
    }
}