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

1. 문제 풀이 아이디어

• 다이나믹 프로그래밍을 사용하여 각 단계에서 최대값을 구하면 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    int solution(int[][] land) {
        int[][] dp = new int[land.length][land[0].length];
        dp[0] = Arrays.copyOf(land[0], land[0].length);
        for (int i = 1; i < land.length; i++) {
            for (int j = 0; j < land[i].length; j++) {
                int max = 0;
                for (int k = 0; k < land[i].length; k++) {
                    if (j == k)
                        continue;
                    max = Math.max(max, dp[i - 1][k]);
                }
                dp[i][j] = land[i][j] + max;
            }
        }
        return Arrays.stream(dp[land.length - 1]).max().getAsInt();
    }
}

3. 정리

• dp라는 2차원 배열을 만들어 각 위치에서의 최대값을 저장하도록 한다.

• dp[0]에 land[0]을 복사해 초기값으로 설정한다.

• 각 행을 순회하면서, 현재 위치(j)와 다른 열(k)에 있는 이전 행의 값들 중 최대값을 찾아 현재 값에 더하고, 이를 dp[i][j]에 저장한다.

• 마지막 행에서 가장 큰 값을 구해 반환한다.