[알고리즘]프로그래머스 12913번 - 땅따먹기

프로그래머스 12913번 - 땅따먹기

프로그래머스 12913번 - https://programmers.co.kr/learn/courses/30/lessons/12913

 

요구사항

1. 1행부터 땅을 밟으며 한 행씩 내려올 때 땅의 점수를 획득합니다.

2. 각 행의 4칸의 땅 중 한 칸만 밟을 수 있으며, 같은 열을 연속해서 밟을 수 없습니다.

3. 마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최댓값을 반환하라.

 

요구사항 분석 및  풀이과정

1. 같은 열을 연속해서 밟을 수 없기 때문에, 각 i번째 행의 j번째 칸의 땅에 왔을 때 얻을 수 있는 점수의 최댓값은 다음과 같다.

 

dp[i][j] = i번째 행의 j번째 칸의 땅에 왔을 때 얻을 수 있는 점수의 최댓값 ( 0 <= i < N, 0 <= j < 4 )

dp[i][j] = board[i][j] + max(board[i-1][k]) ( 0 <= k < 4, k != j )

 

같은 열을 연속해서 밟을 수 없기 때문에 i번째 행의 j번째 칸의 땅에 왔을 때 얻을 수 있는 점수의 최댓값은 이전 행(i-1)의 칸 중 같은 열(j)를 제외한 열의 땅 중 가장 점수가 높은 땅을 거쳐오는 경우입니다.

 

dp[i][j] 의 값 중 board[i][j]는 고정이므로 미리 담아두겠습니다.

 

소스코드 작성

class Solution {
    
    public int solution(int[][] land) {
        int N = land.length;
        int[][] dp = new int[N][4];
        
        for(int row = 0; row < N; row++) {
            for(int col = 0; col < 4; col++) {
                dp[row][col] = land[row][col];
            }
        }

        for(int i = 1; i < N; i++) {
            dp[i][0] += Math.max(Math.max(dp[i-1][1], dp[i-1][2]), dp[i-1][3]);
            dp[i][1] += Math.max(Math.max(dp[i-1][0], dp[i-1][2]), dp[i-1][3]);
            dp[i][2] += Math.max(Math.max(dp[i-1][0], dp[i-1][1]), dp[i-1][3]);
            dp[i][3] += Math.max(Math.max(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
        }

        return Math.max(Math.max(dp[N-1][0], dp[N-1][1]), Math.max(dp[N-1][2], dp[N-1][3]));
    }
}

 

결과

 

소스코드 깃허브 주소

링크

 

마무리

처음 문제를 보았을 때 무작정 DFS로 풀었는데, 시간 초과가 나서 문제를 다시 생각해보았는데, 간단한 점화식 문제였습니다.

 

DFS로 시도했다고해서 그 시도가 나쁘다고 생각하지 않습니다. 백준 같은 경우는 시간제한이 주어져있기 때문에, 우리가 작성해야 하는 알고리즘의 시간 복잡도를 대강 예측을 할 수 있습니다.

 

그렇기 때문에 애초에 무리라고 생각하는 방법은 시도하지 않을 수 있지만, 프로그래머스의 경우는 시간제한이 따로 수치로 주어지지 않기 때문에 시도해보고 그 방법이 올바르지 않다면 빠르게 방향을 튼다면 충분히 좋은 전략이라고 생각합니다.