[프로그래머스] 도둑질

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

동적 계획법 문제이다. 이 문제에서 관건은 모든 집들이 동그랗게 배치되어 있다는 것이다. 따라서 도둑이 첫 번째 집을 턴다면 마지막 집을 털 수 없게 된다. 즉, 첫 번째 집을 터는지에 따라서 정답이 달라질 수 있다는 것이다.

우선은 집이 직선으로 배치되어있다고 생각해보자. 도둑이 1번 집에서 n번 집까지 순서대로 이동한다고 생각해보자. 그렇다면 n번째 집까지 도둑질을 마무리했을 때의 경우는 2가지가 나온다.

1. n-1번째 집을 털고, n번째 집은 털지 않은 경우
2. n-1번째 집을 털지 않고, n번째 집을 턴 경우

이 때 도둑은 항상 최대로 돈을 훔치기 때문에 2번 경우에는 n-2번째 집을 털었을 것이다. 따라서 n번째 집까지 위치했을 때 최댓값은 n-1번째 집까지 털었을 때의 돈 또는 n-2번째 집까지 털었을 때의 돈에 n번째 집을 털어서 얻은 돈이 될 것이다.
즉, dp[n] = max(dp[n-1], dp[n-2] + money[n])이 된다.

이번엔 집이 원형 배치가 된 경우를 생각해보자. 첫 번째 집을 터는지, 안터는지에 따라서 마지막 집을 털 수 있는지, 없는지가 결정된다. 따라서 dp[2][n]으로 메모이제이션을 해서 dp[0][i] 인 경우는 첫 번째 집을 안털었을 경우, dp[1][i]는 첫 번째 집을 털었을 경우라고 생각해서 동적계획법으로 해결했다.

코드

C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> money) {
    int n = money.size();

    vector<vector<int>> dp(2, vector<int>(n, 0));
    dp[0][0] = 0;
    dp[1][0] = money[0];

    for (int i = 1; i < n; i++) {
        dp[0][i] = max(dp[0][i - 1], dp[0][i - 2] + money[i]);
        dp[1][i] = max(dp[1][i - 1], dp[1][i - 2] + money[i]);
    }
    return max(dp[0][n - 1], dp[1][n - 2]);
}

Python3

def solution(money):
    n = len(money)

    dp = [[0] * n for _ in range(2)]
    dp[0][0] = 0
    dp[1][0] = money[0]

    for i in range(2):
        for j in range(1, n):
            dp[i][j] = max(dp[i][j - 1], dp[i][j - 2] + money[j])
    answer = max(dp[0][-1], dp[1][-2])
    return answer