[프로그래머스 Lv4] : 도둑질

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

도둑이 원형으로 배치되어있는 집을 털 때, 털고자하는 집과 인접한 집은 털지않는다. 이때 도둑이 훔칠 수 있는 돈의 최대값을 리턴하는 문제.

 

풀이

먼저 우리가 가장 간단하게 떠올릴 수 있는 방법은 집을 터는 모든 경우의 수를 다 떠올려보는 방법이다.

하지만 집은 최대 1000000개가 있을 수 있으므로 1000000개의 집 중에 이웃하지 않고 1개부터 최대 500000개의 집을 선택하는 경우의 수를 모두 다 따져봐야하기 때문에 엄청난 시간이 소요된다.

따라서 이 방법은 시간초과 오류가 날 것이다.

 

그렇다면 DP를 이용해서 최적의 값을 찾는 방법이 있다.

이때 DP배열의 인덱스는 집의 번호를 의미할 것이다.

하지만 이웃한 집은 훔칠 수 없다는 조건이 있으므로 이전의 집을 방문했는지 여부도 중요하다.

따라서 DP배열을 DP[도둑이 방문했는지 여부][집의 번호] 이렇게 만들 수 있다.

도둑이 방문했는지의 여부는 0, 1로 표현한다.

이것을 바탕으로 점화식을 세워보면

DP[ 1 ][ i ] = DP[ 0 ][ i - 1 ] + money[ i ] 가 된다. (i번째 집을 방문할 경우)

=> i번째 집을 방문하려면 i - 1번째 집은 방문을 하지 않았어야한다.

DP[ 0 ][ i ] = max( DP[ 0 ][ i - 1 ] , DP[ 1 ][ i - 1 ] ) 가 된다. (i번째 집을 방문하지 않을 경우)

=> i번째 집을 방문하지 않았을 경우 훔칠 수 있는 최대 금액은 i - 1번째 집을 방문하거나 방문하지 않은 2가지 경우 중 큰 값과 같다.

 

점화식은 세웠지만 여기서 문제가 있다.

마지막 N-1번째 집(첫 집을 0번째 집이라 생각)에 방문하려 할 때, 점화식에 의해서

DP[ 1 ][ N - 1 ] = DP[ 0 ][ N - 1 ] + money[ N - 1 ] 인데 여기서 DP[ 0 ][ N - 1 ] 에 저장되어 있는 값이 0번째 집을 방문해서 만들어 진 값인지 아닌지 알 수가 없다. 

0번째 집을 방문했을 경우는 마지막 N-1번째 집을 방문하지 못하는데 이것을 체크할 방법이 없다.

 

그래서 내가 생각한 방법은 첫번째 집을 방문했다고 생각하고 N-2번째 집까지 도달했을 때 훔칠 수 있는 최대 금액과

첫번째 집을 방문하지 않았다고 생각하고 N-1번째 집까지 도달했을 때 훔칠 수 있는 최대 금액 중 큰 값을 답으로 생각하기로 했다.

첫번째 집을 방문했다고 생각했을 때는 왜 N-1번째가 아닌 N-2번째까지 도달했을 때 최대값을 체크하느냐

어짜피 첫번째 집을 방문했다면 마지막 집은 방문하지 못하기때문에 마지막 집은 의미가 없다.

 

코드 작성

#include <string>
#include <vector>
#include <string.h>
using namespace std;
const int MAX_N = 1000000 + 5;
int DP[2][MAX_N];
int solution(vector<int> money) {
    int answer = 0;
    int N = money.size(); //집의 개수
    DP[0][0] = 0;
    DP[1][0] = 0;
    for(int i = 1; i<N; i++){
        DP[0][i] = max(DP[1][i-1], DP[0][i-1]);
        DP[1][i] = DP[0][i-1] + money[i];
    }
    answer = max(DP[1][N-1], DP[0][N-1]);
    memset(DP,0,sizeof(DP));
    DP[1][0] = money[0];
    for(int i = 1; i<N-1; i++){
        DP[0][i] = max(DP[1][i-1], DP[0][i-1]);
        DP[1][i] = DP[0][i-1] + money[i];
    }
    answer = max(answer, max(DP[0][N-2], DP[1][N-2]));
    return answer;
}