땅따먹기_복습

2026.08.16

문제 풀이

1차 실행 오류

---

0.0/100

시간 초과 오류

---

시간 초과 원인 분석

행의 개수가 100,000개 이하인 배열에 DFS를 사용한 것이 원인

---

class Solution {
    private int answer = 0;
    int solution(int[][] land) {
        dfs(land, 0, 0, 0);
        
        return answer;
    }
    private void dfs(int land[][], int row, int col, int sum) {
        answer = Math.max(answer, sum);
        if (row >= land.length) {
            return;
        }
        
        for (int i = 0; i < land[row].length; i++) {
            if (i == col) {
                continue;
            }
            dfs(land, row + 1, col, sum + land[row][i]);    
        }
    }
}

나의 코드

---

소요 시간: 45분
시간 복잡도: $O(n)$

---

코드 분석

이전 행과 현재 행 사이에서 가장 큰 값을 찾아 저장하여 가장 큰 값을 찾아냄

---

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

AI 코드

---

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

---

코드 분석

기존 나의 코드에서 3중 for문을 사용하던 방식에서
이전 행의 첫 번째로 큰 값과 두 번째로 큰 값을 미리 구해서
이번 행의 가장 큰 값과 더하는 방식을 사용하여 개선함

---

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

        for (int i = 1; i < n; i++) {
            // 직전 행의 1등 값/인덱스와 2등 값
            int best = Integer.MIN_VALUE, second = Integer.MIN_VALUE, bestIdx = -1;
            for (int j = 0; j < c; j++) {
                if (prev[j] > best) { second = best; best = prev[j]; bestIdx = j; }
                else if (prev[j] > second) { second = prev[j]; }
            }

            int[] cur = new int[c];
            for (int j = 0; j < c; j++) {
                cur[j] = land[i][j] + (j == bestIdx ? second : best);  // 같은 열이면 2등을 사용
            }
            prev = cur;   // 행 하나만 굴린다 → 공간 O(1)
        }

        int answer = Integer.MIN_VALUE;
        for (int v : prev) answer = Math.max(answer, v);
        return answer;
    }
}

문제 풀이 후기

DP 문제가 너무 어렵다고 느껴진다.
AI 분석을 해 본 결과 다른 자료구조 문제에 비해 풀어 보았던 문항 수가
현저히 적어서 손에 익지 않았다는 것이 그 원인이다.

나의 학습법을 보면 많은 경험을 토대로 익숙해지는 것이 가장 수월하게
배울 수 있는 길이라고 생각한다.