땅따먹기

ㅇ 문제설명

 

ㅇ 첫번째 시도

public static int solution(int[][] land) {
        //맨첫번째 행에서 4가지 경우의수를 구한다.
        int total = 0;
        int maxIndex = 0;

        for(int i = 0; i < land.length; i++){
                if(i == 0){
                    total += maxArrNoEx(land[i]);
                    maxIndex = findIndex(land[i],total);
                }else{
                    total += maxArr(land[i],maxIndex);
                }
        }
        return total;
    }
    public static int maxArr(int[] arr, int except){
        int maximum = 0;
        for(int a = 0; a < arr.length; a++){
            if(a == except){
                continue;
            } else if (maximum < arr[a]) {
                maximum = arr[a];
            }
        }
        return maximum;
    }
    public static int maxArrNoEx(int[] arr){
        int maximum = 0;
        for(int a = 0; a < arr.length; a++){
             if (maximum < arr[a]) {
                maximum = arr[a];
            }
        }
        return maximum;
    }
    public static int findIndex(int[] arr, int targetValue) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == targetValue) {
                return i;  // 값을 찾았으면 해당 인덱스 반환
            }
        }
        return -1;  // 배열 전체를 검색한 후에도 값을 찾지 못했다면 -1 반환
    }

다 메서드로 만들어서 풀어봤다.

예시로 주어진[[1,2,3,5],[5,6,7,8],[4,3,2,1]] 여기서

i = 0 일때, 1,2,3,5중 가장 큰걸 찾아 total에 넣고, 그게 몇번째 index인지 찾고, 다음 행에서 그 index를 제외하고 가장 큰걸 찾아서 total에 누적으로 더해준다.

그래서 5,7,4 를 더해서 16이 나왔다. 풀면서도 아. 이건 반례가 너무 많을거같은데? 했더니 진짜로 이정도일줄이야..

충격이다.

 

ㅇ 정답 풀이

나처럼 풀면 안된다. 이문제는 DP를 이용해 풀어야한다고 한다.

https://www.educative.io/answers/what-is-dynamic-programming

동적 프로그래밍(DP)은 복잡한 문제를 간단하고 작은 하위 문제로 나누어 해결하는 알고리즘 디자인 기법이다. DP는 주로 최적화 문제에 사용된다. 각 행과 열을 순회하면서 이전 행에서 최대 점수를 계산하는 방식으로 작동하고, 결과적으로 마지막 행에서 가능한 최대 점수를 반환한다.

public int solution(int[][] land) {
        int n = land.length;
        int m = 4; // 열의 개수는 항상 4
        
        // 각 행의 최대 점수를 저장할 DP 배열을 초기화
        int[][] dp = new int[n][m];
        for (int i = 0; i < m; i++) {
            dp[0][i] = land[0][i];
        }

        // DP로 최대 점수 계산
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int maxPrev = 0; // 이전 행의 같은 열을 제외한 최대값
                for (int k = 0; k < m; k++) {
                    if (k != j) {
                        maxPrev = Math.max(maxPrev, dp[i-1][k]);
                    }
                }
                dp[i][j] = land[i][j] + maxPrev;
            }
        }

        // 마지막 행에서 최대값을 찾음
        int maxScore = 0;
        for (int i = 0; i < m; i++) {
            maxScore = Math.max(maxScore, dp[n-1][i]);
        }

        return maxScore;
    }

 

완전히 잊고있었던 알고리즘이다. 다시 공부해보자.