땅따먹기_복습2

2026.10.01

문제 풀이

나의 코드

---

소요 시간: 1시간 50분
시간 복잡도: $O(N)$

---

class Solution {
    int solution(int[][] land) {
        int[][] sum = new int[land.length][land[0].length];
        for (int i = 0; i < 4; i++) {
            sum[0][i] = land[0][i];
        }
        
        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, land[i][j] + sum[i - 1][k]);
                }
                sum[i][j] = max;
            }
        }
        int answer = 0;
        for (int i = 0; i < sum[sum.length - 1].length; i++) {
            answer = Math.max(answer, sum[sum.length - 1][i]);
        }
        return answer;
    }
}

AI 코드

---

시간 복잡도: $O(N)$

---

코드 분석

전체적인 구조는 같으나,
2차원 배열을 1차원의 2개의 배열로 나눔으로 인해
필요 없는 행을 가지고 있지 않음으로 인해 메모리를 아꼈다.

---

import java.util.Arrays;

class Solution {
    int solution(int[][] land) {
        int[] prev = land[0].clone();

        for (int i = 1; i < land.length; i++) {
            int[] cur = new int[4];
            for (int j = 0; j < 4; j++) {
                int best = 0;
                for (int k = 0; k < 4; k++) {
                    if (j != k) best = Math.max(best, prev[k]);
                }
                cur[j] = land[i][j] + best;
            }
            prev = cur;   // 현재 행이 다음 행의 '이전 행'이 됨
        }
        return Arrays.stream(prev).max().getAsInt();
    }
}

문제 풀이 후기

class Solution {
    int solution(int[][] land) {
        int[] sum = new int[land[0].length];
        for (int i = 0; i < 4; i++) {
            sum[i] = land[0][i];
        }
        
        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, land[i][j] + sum[k]);
                }
                sum[j] = max;
            }
        }
        int answer = 0;
        for (int i = 0; i < sum.length; i++) {
            answer = Math.max(answer, sum[i]);
        }
        return answer;
    }
}

---

30분만에 해당 코드까지 구현한 후에 그 뒤로 갈피를 잡질 못했다.
반복문이 잘못된건지,
max 에 값을 대입하는 과정에서 배열에 들어가는 변수가 잘못됐는지,
혹은 sum[j] = max 가 잘못됐는지 아무리 생각해봐도 답이 나오질 않았다.

결론을 말하자면 sum[j] = max 해당 부분이 잘못됐었다.
j = 0 일 때에는 정상 동작하다가 j > 1 이 되면서부터 문제가 발생한다.

만약 입력된 배열이 [[1, 2, 3, 5], [5, 6, 7, 8], [4, 3, 2, 1]]
이라고 할 때, [5, 6, 7, 8] 에서 첫번째 원소인 5까지는
이전 행 값인 [1, 2, 3, 5] 와 5의 합을 제대로 비교하지만,
두번째 원소인 6의 경우에는 이전 행의 0번째 행이 5가 만들 수 있는 가장 큰 값이 반영된 현재 행을 기준으로 계산이 되었던 것이다.

값을 하나하나 넣어가면서 진행했는데 아무리 해봐도 이상한 점을 찾지 못했다.
집중력이 너무나도 최악이다. 솔직히 왜 이거 하나를 제대로 못본건지 너무나도 이해가 안되고 짜증이 난다.

문제의 정답을 보고 이해하는 능력이 아니라, 문제를 스스로 찾는 능력이 필요하다.
AI를 활용하는 것은 좋지만,
나 자신도 생각하고 문제를 해결할 줄 아는 능력이 필요하다.