[PCCP JAVA] 땅따먹기

문제 링크 👉 https://school.programmers.co.kr/learn/courses/30/lessons/12913

---

📌 문제 설명

땅따먹기 게임 규칙

• 땅은 N행 × 4열
• 각 칸에 점수가 적혀 있음
• 1행에서 시작하여 한 행씩 내려오며 한 칸만 선택
• 같은 열을 연속해서 밟을 수 없음
• 마지막 행까지 내려왔을 때 얻을 수 있는 점수의 최댓값을 구해야 함

예시:

[ [1, 2, 3, 5],
  [5, 6, 7, 8],
  [4, 3, 2, 1] ]

가능한 최적 경로: (5) → (7) → (4)
총점: 16

---

❌ 잘못된 접근 — BFS/DFS 완전탐색

처음에 많이 하는 실수는 모든 경로를 전부 탐색하는 방법입니다.

• 각 행에서 최대 4가지 선택
• 경로 수 = 4^N → N이 커지면 (최대 100,000) 시간/메모리 폭발

따라서 완전탐색은 불가능하고, 이전 행의 정보만 사용하면 되는 DP가 정답입니다.

---

💡 핵심 아이디어 — DP 점화식

dp[r][c] = r행 c열에 도착했을 때의 누적 최댓값

점화식:

dp[r][c] = land[r][c] + max(dp[r-1][k])   단, k != c

즉, 같은 열을 제외한 이전 행의 최댓값만 더해주면 됩니다.

---

🏆 최적 풀이 1 — In-place DP

land 배열 자체를 DP 테이블로 사용하여 덮어씁니다.
왜 가능?

• r행 계산 시, r-1행 정보만 참조 → 이전 행 값은 이미 확정됨
• 따라서 별도 배열 없이 덮어써도 무방

구현 코드

import java.util.*;

class Solution {
    public int solution(int[][] land) {
        int n = land.length;
        for (int r = 1; r < n; r++) {
            land[r][0] += Math.max(land[r-1][1], Math.max(land[r-1][2], land[r-1][3]));
            land[r][1] += Math.max(land[r-1][0], Math.max(land[r-1][2], land[r-1][3]));
            land[r][2] += Math.max(land[r-1][0], Math.max(land[r-1][1], land[r-1][3]));
            land[r][3] += Math.max(land[r-1][0], Math.max(land[r-1][1], land[r-1][2]));
        }
        int last = n - 1;
        return Math.max(
            Math.max(land[last][0], land[last][1]),
            Math.max(land[last][2], land[last][3])
        );
    }
}

---

📊 예제 동작 과정

입력:

[ [1, 2, 3, 5],
  [5, 6, 7, 8],
  [4, 3, 2, 1] ]

1행 (시작값) → [1, 2, 3, 5]

2행 갱신:

• 0열: 5 + max(2,3,5) = 10
• 1열: 6 + max(1,3,5) = 11
• 2열: 7 + max(1,2,5) = 12
• 3열: 8 + max(1,2,3) = 11
  → [10, 11, 12, 11]

3행 갱신:

• 0열: 4 + max(11,12,11) = 16
• 1열: 3 + max(10,12,11) = 15
• 2열: 2 + max(10,11,11) = 13
• 3열: 1 + max(10,11,12) = 13
  → [16, 15, 13, 13]

마지막 행 최댓값 = 16

---

🧮 복잡도 분석

• 시간복잡도: O(4N) = O(N)
• 공간복잡도: O(1) (land 배열 재사용)
• 안전성: 점수 ≤ 100, N ≤ 100,000 → 최댓합 ≤ 10,000,000 → int 범위 내

---

⚠️ 주의할 점

• 원본 land 보존이 필요하면, 이 방식 대신 롤링 배열 DP 사용
• 열 개수가 변하면 top1/top2 추적 기법을 써야 하지만, 이 문제는 고정 4열이라 단순 구현이 가능
• Greedy(그때그때 최대값 선택)는 오답 가능성 있음

---

✏️ 결론

이 문제는 전형적인 행 단위 DP 누적 문제입니다.
“같은 열 제외한 이전 행의 최댓값”만 찾으면 되므로
**O(N)**으로 빠르게 해결할 수 있습니다.

In-place 방식은 코드 간결 + 공간 최적화까지 가능하니,
PCCP 대비용으로 꼭 외워두세요.

---

이제 이 방식만 기억하면 비슷한 규칙의 N행 × M열 게임판 최적 경로 문제도 손쉽게 풀 수 있습니다.
다음엔 M이 변하는 버전과 top1/top2 최적화도 다뤄보겠습니다.