[틀림] 프로그래머스 도둑질 // 노드스킵 dp

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

프로그래머스

* dfs dp 풀이

• 시행착오
  • 무조건 집을 다 도둑질하는게 이득아닌가?
  • 아님, 0원인집 도둑질 -> i+1에 100만원 집을 못텀

• 결국 idx번째 집을 턴다, 안턴다로 완탐필요
  • 현재집을 턴다 -> 다음집은 cur+2 // cur+1을 못터는걸 여기서 구현
  • 현재집을 안턴다 -> 다음집은 cur+1
  • 다음집에서도 재귀적으로 위 2경우 탐색

• 예외처리
  • 첫번째 집을터는경우, 마지막 집을 털수없음 예외처리

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[1000000+4]; // dp[cur][st] 형태로 변경
vector<int> money;

int dfs(int cur, int st) {
    
    if (cur == n-1 && st == 0) return 0; // 첫 집 선택 시 마지막 집 불가
    if (cur >= n) return 0;
    if (dp[cur] != -1) return dp[cur];

    int& ret = dp[cur];
    ret=-1;
    ret = max(ret, dfs(cur + 2, st) + money[cur]); //현재 집선택
    ret = max(ret, dfs(cur + 1, st)); // 현재 집 안선택
    
    return ret;
}


int solution(vector<int> _money) {
    money = _money;
    n = money.size();
    // if (n == 1) return money[0];
    
    // Case 1: 첫 번째 집 선택 (마지막 집 불가)
    memset(dp, -1, sizeof(dp));
    int case1 = dfs(0, 0);
    
    // Case 2: 첫 번째 집 미선택 (마지막 집 가능)
    memset(dp, -1, sizeof(dp));
    int case2 = dfs(1, 1);
    
    return max(case1, case2);
}

 

* for문 dp

• i-1 vs i-2 + 내돈 비교
• 직전돈을 택하는대신, 현재돈을 못텀 vs 직전돈을 버리고 현재돈을 택함

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

int solution(vector<int> money) {
    int n = money.size();
    if (n == 1) return money[0];

    // 첫 번째 집을 선택한 경우
    vector<int> dp1(n, 0);
    dp1[0] = money[0];
    dp1[1] = money[0];
    for (int i = 2; i < n - 1; ++i) {
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + money[i]);
    }

    // 첫 번째 집을 선택하지 않은 경우
    vector<int> dp2(n, 0);
    dp2[0] = 0;
    dp2[1] = money[1];
    for (int i = 2; i < n; ++i) {
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + money[i]);
    }

    return max(dp1[n - 2], dp2[n - 1]);
}