Programmers | Level 2 | 땅따먹기

Programmers | Level 2 | 땅따먹기

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Dynamic Programming

󰧭 Description

땅따먹기 게임은 N행 4열로 이루어진 땅에서 최대 점수를 얻는 것이 목표입니다. 각 행에는 4개의 칸이 있으며, 각 칸에는 점수가 적혀 있습니다. 플레이어는 첫 번째 행에서 시작하여 한 행씩 아래로 내려오면서 각 행에서 한 칸씩 밟아야 합니다. 단, 같은 열을 연속해서 밟을 수 없습니다. 마지막 행까지 도달했을 때 얻을 수 있는 최대 점수를 구하세요.

 Constraints

• 행의 개수 N: 100,000 이하의 자연수
• 열의 개수는 4개
• 점수는 100 이하의 자연수

󰦕 Examples

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

Solutions

󰘦 Code

import java.util.*;

class Solution {

    public int solution(int[][] land) {
        int n = land.length;

        for (int i = 1; i < n; i++) {
            land[i][0] += maxOf(land[i-1][1], land[i-1][2], land[i-1][3]);
            land[i][1] += maxOf(land[i-1][0], land[i-1][2], land[i-1][3]);
            land[i][2] += maxOf(land[i-1][0], land[i-1][1], land[i-1][3]);
            land[i][3] += maxOf(land[i-1][0], land[i-1][1], land[i-1][2]);
        }

        return maxOf(land[n-1][0], land[n-1][1], land[n-1][2], land[n-1][3]);
    }

    private int maxOf(int... values) {
        int maxValue = Integer.MIN_VALUE;
        for (int value : values) {
            if (value > maxValue) maxValue = value;
        }
        return maxValue;
    }
}

 Approaches

이 문제는 각 행에서 최적의 선택을 반복적으로 계산하고, 그 결과를 바탕으로 다음 행에서의 최적 선택을 결정해야 하는 다이나믹 프로그래밍(Dynamic Programming) 접근법을 사용하여 해결할 수 있습니다. 아래 단계별로 문제 해결 과정을 상세히 설명합니다:

1. 행의 개수 계산 및 초기 변수 설정

먼저, 주어진 땅 land[][] 배열의 크기를 파악하여, 총 몇 개의 행이 있는지를 계산합니다. 이 정보는 이후 반복문에서 각 행을 순차적으로 탐색하는 데 사용됩니다. land.length를 사용하여 땅의 행 수를 가져오고, 이를 변수 n에 저장합니다.

// land 배열의 행 개수를 계산하여 n에 저장
int n = land.length;

• land.length는 땅따먹기 게임에서 주어진 땅의 행 수를 나타내며, 이 값을 기반으로 반복문을 설정하여 모든 행을 탐색하게 됩니다. 이 변수 n은 게임의 진행 상황을 제어하는 역할을 합니다.

2. 이전 행을 기반으로 현재 행 점수 갱신

이 단계에서는 각 행을 순차적으로 탐색하며, 현재 행의 각 칸에서 선택할 수 있는 최대 점수를 갱신합니다. 중요한 개념은 이전 행에서 동일한 열을 연속해서 선택할 수 없다는 점입니다. 따라서, 각 칸의 점수를 갱신할 때는 이전 행에서 동일한 열을 제외한 나머지 세 열 중에서 최대 점수를 선택하여 현재 점수에 더하게 됩니다. 이렇게 갱신된 land[i][j] 값은 해당 칸까지의 누적된 최대 점수를 의미합니다.

for (int i = 1; i < n; i++) {
    // 이전 행의 0번째 열을 제외한 1, 2, 3번째 열 중 최대값을 더한 0번째 열
    land[i][0] += maxOf(land[i-1][1], land[i-1][2], land[i-1][3]);
    // 이전 행의 1번째 열을 제외한 0, 2, 3번째 열 중 최대값을 더한 1번째 열 
    land[i][1] += maxOf(land[i-1][0], land[i-1][2], land[i-1][3]);
    // 이전 행의 2번째 열을 제외한 0, 1, 3번째 열 중 최대값을 더한 2번째 열
    land[i][2] += maxOf(land[i-1][0], land[i-1][1], land[i-1][3]);
    // 이전 행의 3번째 열을 제외한 0, 1, 2번째 열 중 최대값을 더한 3번째 열
    land[i][3] += maxOf(land[i-1][0], land[i-1][1], land[i-1][2]);
}

• 모든 행의 순차적 탐색: 이 루프는 첫 번째 행을 제외한 모든 행을 순차적으로 탐색하며, 각 행의 모든 칸에 대해 누적된 최대 점수를 계산합니다.
• 이전 행의 최적 점수 선택:
  • 각 칸의 점수를 갱신할 때, 이전 행에서 같은 열을 제외한 나머지 세 열 중 최대 점수를 선택합니다.
  • 예를 들어, 현재 i번째 행의 첫 번째 열 land[i][0]은 이전 행의 첫 번째 열을 제외한 나머지 열 중 가장 높은 점수를 더해 갱신됩니다. 이 과정은 연속된 행에서 같은 열을 선택할 수 없도록 하는 게임의 규칙을 반영한 것입니다.
  • 이전 행의 가장 높은 점수를 구하는 로직은 maxOf() 함수를 통해 분리하였습니다.
• 현재 행의 점수 갱신: 각 칸 land[i][j]는 앞서 계산한 이전 행의 최적 점수를 더하여 갱신됩니다. 이 갱신된 값은 그 칸까지의 누적된 최대 점수를 의미하며, 이후 행의 계산에서 사용됩니다. 이를 통해 각 행에서 가능한 최적의 경로를 누적해 나갑니다.
• 반복적 계산: 이 과정은 모든 행에 대해 반복되며, 마지막 행에 도달하면 각 칸에는 그 칸까지 도달할 수 있는 경로 중 최대 점수가 저장됩니다.

반복적인 코드를 줄이기 위해, 가변 인자를 받아 최대값을 계산하는 maxOf() 함수는 다음과 같이 구현되어 있습니다:

// 가변 인자를 받아 최대값 반환
private int maxOf(int... values) {
    int maxValue = Integer.MIN_VALUE;
    for (int value : values) {
        if (value > maxValue) maxValue = value;
    }
    return maxValue;
}

• 가변 인자 처리: int... values는 함수가 호출될 때 전달되는 여러 개의 정수를 배열로 처리합니다. 이는 함수가 유연하게 다양한 수의 인자를 받을 수 있게 합니다.
• 최대값 계산: 함수는 전달된 값들 중 가장 큰 값을 찾습니다. 루프를 사용해 각 값을 순회하며, 현재까지 발견한 최대값을 갱신해 나갑니다.
• 결과 반환: 마지막으로 최대값을 반환하여, 이 값을 통해 각 행의 최적의 점수를 결정할 수 있습니다.

3. 최종 결과 계산 및 반환

모든 행을 탐색한 후, 마지막 행의 네 개의 칸 중 가장 큰 값을 선택하여 반환합니다. 이 마지막 행에 있는 값들은 이전 모든 행에서 누적된 합산이 반영된 결과이며, 각 칸에는 해당 칸까지 도달할 수 있는 경로 중 최대 점수가 쌓여 있습니다. 따라서, 마지막 행에서 가장 큰 값이 전체 게임에서 얻을 수 있는 최종 최대 점수를 나타냅니다.

// 마지막 행의 모든 열에서 최대값을 찾아 반환
return maxOf(land[n-1][0], land[n-1][1], land[n-1][2], land[n-1][3]);

• 마지막 행의 최대값 계산: 마지막 행의 네 칸 중에서 가장 큰 값을 선택하여 반환합니다. 이 값은 이전 단계에서 누적된 합산이 반영된 결과로, 각 경로의 최대 점수가 최종적으로 누적된 것입니다.
• 결과 반환: 계산된 최대값을 반환하여, 전체 게임에서 얻을 수 있는 최대 점수를 최종적으로 도출합니다.

이 방법을 통해 문제를 효율적으로 해결할 수 있습니다. 다이나믹 프로그래밍을 사용함으로써 시간 복잡도 O(N)으로 각 행의 최적의 선택을 반복적으로 계산하여, 모든 경우를 빠짐없이 고려하면서도 중복 계산을 최소화할 수 있습니다.

󰄉 Complexity

• ⏳ TC: O(n)
• 💾 SC: O(1)

이 알고리즘의 시간 복잡도는 O(n)입니다. 이는 주어진 land 배열의 각 행을 한 번씩 순차적으로 처리하기 때문입니다. 각 행의 칸을 갱신하기 위해 이전 행의 최적 값을 참조하는 과정이 포함되며, 이 과정은 모든 행에 대해 한 번씩 수행됩니다. 따라서, 전체적인 연산은 N에 비례하여 진행됩니다.

공간 복잡도는 O(1)로 매우 효율적입니다. 새로운 배열이나 추가적인 메모리 공간을 사용하지 않고, 기존의 land 배열을 직접 수정하면서 결과를 갱신합니다. 따라서, 추가적인 메모리 사용이 거의 없으며, 전체 문제를 해결하는 데 필요한 공간은 상수 시간에 비례합니다.