프로그래머스 도둑질 java

전수민

Nov 19, 2025

TABLE OF CONTENTS

1. 문제에 대하여 📦

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

집이 원형 형태의 공간에 하나씩 배치되어 있다. 집마다 돈을 보유하고 있다.
도둑이 집을 도둑질 할 건데, 하나의 집을 도둑질 하면 양쪽으로 이웃한 집은 도둑질 할 수 없다. 이때, 도둑질로 털 수 있는 최대의 금액을 구하라.

(1) 조건 분석 📊

문제에서는 집이 배열로 주어지는데, 여기서 배열의 맨 처음 값과 배열의 맨 끝 값이 이웃한다는 것을 이해하고 있어야 한다.

2. 코드가 나오기까지 🛠️

KEY WORD: DP

해당 문제에서는 초기값을 구해놓고, 점화식을 활용해 Bottom up 할 예정이다.

(1) 점화식 구하기

i 번쨰 집을 골랐을 때의 최대 금액을 구한다고 해보자. 이때 문제의 규칙 때문에 i-1번째 집은 선택하지 못한다. 그렇다면 선택지는 i-2와 i-3 번쨰 집을 골랐을 떄의 최대 금액에 현재 집의 금액을 더하는 것이 남았을 것이다.
i-4번째 집을 고려했을 때 최대 금액은 i-2번째 집을 선택하는 경우의 수에서 이미 고려되어 있기 떄문에, i-4부터 그 뒤에 있는 집들은 선택지에 넣을 필요가 없다. 따라서 점화식을 생각해본다면 다음과 같을 것이다.


dp[i] = money[i] + Math.max(dp[i-2], dp[i-3]);

(2) DP 분리해서 계산하기

첫 번쨰 집을 고려하는 경우의 수와 고려하지 않은 경우의 수를 나눠서 생각해야 한다. 첫 번째 집을 고르면 맨 끝의 집을 고를 수 없기 때문이다. 만약 이 두 경우의 수를 하나의 dp 배열에서 고려한다면, dp[N-1] 의 값이 dp[0] (첫 번쨰 집을 고려헀을 떄, 최대 금액)이 포함되므로, 명확한 답을 구할 수가 없다.

(3) 답이 될 수 있는 후보지

첫 번째 집을 고려한 배열을 first, 고려하지 않은 배열을 secoend라고 했을 때. first 배열의 N-2, N-3, second 배열의 N-1, N-2 번쨰 값이 후보군이 될 수 있다. 왜냐하면 이웃한 집은 고를 수 없기 때문에, DP 누적이 한 곳으로 안 모이고, 배열 끝 두 개의 원소에 후보군이 각각 존재하기 때문이다

(4) 시간복잡도 분석 ⏳

N을 집의 개수라고 한다면, 최대 배열을 한 번 훑기 때문에 O(N)이다.

3. 코드 🌐

(1) SUDO CODE 💬


1. 배열 두 개로 나누기
2. 각 배열마다 점화식으로 답 누적
3. 각 배열의 후보군 모두 비교해서 최대값 구하기

(2) JAVA CODE ☕


import java.util.*;

class Solution {
    public int solution(int[] money) {
        int [] fir = new int [money.length];
        int [] sec = new int [money.length];

        fir[0] = money[0];
        fir[2] = money[2] + money[0];
        sec[1] = money[1];
        sec[2] = money[2];

        for(int i = 3; i < money.length; i++){
            fir[i] = money[i] + Math.max(fir[i-2], fir[i-3]);
            sec[i] = money[i] + Math.max(sec[i-2], sec[i-3]);
        }
        int N = money.length;
        return (int) Math.max(Math.max(fir[N-2], fir[N-3]), Math.max(sec[N-1], sec[N-2]));
    }
}