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

문제

1. 문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

 

2. 제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

 

풀이

• 만약 완전탐색으로 하고자 했다면?
  • 반복을 index 0부터 n-1까지 돌면서 해당 집에서 시작해서 나타나는 최대의 money를 구할 수 있음
  • 하지만 index 2를 고른다면, 집의 개수가 짝수일 때 index 0을 고를 수 있고 홀수일 때 index 1을 고를 수 있음
    • 고로 index 0과 1만 고려하면 됨
• DP
  • 3번째 <재귀함수> 코드
    • top-down 방식으로 해당 index에서의 maxMoney 구해서 저장
  • 점화식 풀이 코드
    • DP는 배열을 이용한 점화식 풀이를 먼저 생각해보고 안되면 재귀함수로 돌리자.
    • 1차원 배열(arr)에서 집의 index를 배열의 index, 값을 최대 money로 보자.
    • 1번째 top-down (배열으로 봤을 때, 마지막 요소를 구하기 위해 이전 요소를 이용) 코드
      • 현재 index를 i라 할 때,
      • arr[i] = max(arr[i-2]+ money[i], arr[i-1])
    • 2번째 bottom-up (배열으로 봤을 때, 첫번째 요소를 이용해서 마지막 요소들을 생성) 코드
      • arr[i+2] = max(arr[i+2], arr[i] + money[i+2])
      • arr[i+1] = max(arr[i+1], arr[i])

 

코드

1. <점화식 top-down>

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
int memo[1000001];
int memo2[1000001];

int solution(vector<int> money) {
    // top-down
    int answer = 0;
    memset(memo, -1, sizeof(memo));
    memset(memo2, -1, sizeof(memo2));

    int size = money.size();

    memo[0] = money[0];
    memo[1] = memo[0];
    for(int i=2; i<size-1; i++){ // 첫번째 요소에서 시작하면 마지막 요소 제외
        memo[i] = max(memo[i-2] + money[i], memo[i-1]);
    }

    memo2[0] = 0;
    memo2[1] = money[1];
    for(int i=2; i<size; i++){ // 두번째 요소에서 시작하면 마지막 요소 포함
        memo2[i] = max(memo2[i-2] + money[i], memo2[i-1]);
    }

    answer = max(memo[size-2], memo2[size-1]);

    return answer;
}

 

2. <점화식 bottom-up>

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
int memo[1000001];
int memo2[1000001];

int solution(vector<int> money) {
    // bottom-up
    int answer = 0;
    memset(memo, -1, sizeof(memo));
    memset(memo2, -1, sizeof(memo2));

    int size = money.size();

    memo[0] = money[0];
    memo[1] = memo[0];
    for(int i=0; i<size-2; i++){
        memo[i+2] = max(memo[i+2], memo[i] + money[i+2]);
        memo[i+1] = max(memo[i+1], memo[i]);
        // size-2를 구하는데 최대 size-1까지 나오므로 필요없는 연산이 추가됨
    }

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

    answer = max(memo[size-2], memo2[size-1]);

    return answer;
}

 

3. 오답코드 <재귀함수>

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

int N;
vector<int> moneyArr;
int memo[1000001];

bool isBitmapEmpty(vector<int>& vec) {
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i] == 1)
            return false;
    }
    return true;
}

int stillMoney(vector<int>& bitmap, int prev) {
    if (isBitmapEmpty(bitmap)) // 더이상 훔칠수 있는 집이 없으면 0 return
        return 0;

    int maxMoney = 0; // 최대 훔친 돈
    for (int i = prev; i < N; i++) { // 한바퀴 돌게 되면 자동으로 for문 종료
        vector<int> houses(bitmap);
        if (houses[i] == 0) // 훔칠 수 없으면
            continue;

        if (memo[i] != -1) {
            // memo가 있으면
            maxMoney = max(maxMoney, memo[i]);
            continue;
        }

        houses[i] = 0; // 이미 훔쳤으므로 더이상 훔칠 수 없음
        houses[(i - 1 + N) % N] = 0; // 이전 집은 인접해있으므로 훔칠 수 없음
        houses[(i + 1) % N] = 0; // 이후 집

        int tmpMoney = stillMoney(houses, i + 2) + moneyArr[i];
        if (maxMoney < tmpMoney) {
            maxMoney = tmpMoney;
        }
    }
    memo[prev] = maxMoney;
    return maxMoney;
}

int solution(vector<int> money) {
    moneyArr = money;
    N = moneyArr.size(); // 집의 개수 저장
    vector<int> bitmap(N, 1); memset(memo, -1, sizeof(memo));
    int res = stillMoney(bitmap, 0);

    bitmap = vector<int>(N, 1); memset(memo, -1, sizeof(memo));
    res = max(res, stillMoney(bitmap, 1));
    return res;
}

 

결과

1. <점화식 top-down>

 

2. <점화식 bottom-up>

 

3. <재귀 - 효율성 0점>

bitmap으로 체크할 필요 없는데 체크해서 그런 듯 하다.