공부하는 식빵맘 👱‍♀️

공부하는 식빵맘 👱‍♀️

반갑습니다 :)

[고득점Kit][DP] 도둑질 ⭐⭐⭐⭐

Date:     Updated:

카테고리:

태그:

[DP] 도둑질

난이도 ⭐⭐⭐⭐

문제

image

이 문제를 DP 적으로 생각하는게 어려웠다. 배울게 많았던 문제이니 반복해서 보자!!


풀이

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

using namespace std;

int solution(vector<int> money) {
    int answer = 0;
    int tempMax = 0;
    vector<int> dp(money.size());  // 0 부터 차례대로 해당 원소까지 털었을 때의 돈의 최댓값
    
    // 1. 첫 번째 집을 털었을 때(마지막 집은 털지 못한다.)의 전체
    dp[0] = money[0];
    dp[1] = dp[0];
    for(int i = 2; i < money.size() - 1; i++)
        dp[i] = max(dp[i - 1], dp[i - 2] + money[i]);
    dp.back() = dp[dp.size() - 2];
    tempMax = *max_element(dp.begin(), dp.end());
    
    // 2. 첫 번째 집을 털지 않았을 때의 전체
    dp[0] = 0;
    dp[1] = money[1];
    for(int i = 2; i < money.size(); i++)
        dp[i] = max(dp[i - 1], dp[i - 2] + money[i]);
    
    // 1, 2 두 경우 중 Max
    answer = max(tempMax, *max_element(dp.begin(), dp.end()));
    
    return answer;
}

동적 계획법은 피보나치 수열 구하는 것과 비슷하다는 것 기억하자~~~

A B C D 이렇게 나란히 집이 동그랗게 마주보며 있을 때, A 를 털었다면 A 의 양옆에 있는 B 와 D 의 방범 장치가 울리므로 B 와 D 는 털 수 없게 된다. A 와 이웃하지 않은 C 만 털 수 있다.

  • 점화식 👉 dp[i] = max(dp[i - 1], dp[i - 2] + money[i])
    • dp[i] : 0 인덱스를 가진 집부터 i 인덱스를 가진 집'까지' 의 모든 경우를 고려해서 누적 계산해온 돈의 최대 값
      • 현재 집의 운명은 다음과 같이 두가지 경우다.
        • 현재 집을 털지 않는 경우 👉 0 ~ 이전집까지의 돈의 최대값을 물려받는다.
          • dp[i - 1]
        • 이전 집은 털지 않고, 현재 집을 터는 경우 👉 0 ~ 이전이전집까지의 돈의 최대값에 현재 집의 돈을 더한다. 이전집까지의 최대값은 고려하지 않는다.
          • dp[i - 2] + money[i]
      • 위 두 경우 중 더 큰 돈을 가지게 되는 쪽이 i 인덱스를 가진 집까지의 집들을 터는 모든 경우들의 돈의 최대값이 될 것이다.
        • dp[i - 1]가 더 크면 dp[i] 👉 dp[i - 1]
        • dp[i - 2] + money[i]가 더 크면 dp[i] 👉 dp[i - 2] + money[i]
    • 매 집마다 현재 집을 털었을 때⭕, 안털었을때❌ 두가지 경우가 있을 텐데 이 중 더 큰 최대값을 가지는 경우를 채택하면 된다.
  • 첫 번째집, 마지막 번째 집 동시에 둘 다 훔칠 수는 없기 때문에 아래와 같이 두가지 조건으로 나누어 동적계획법 계산을 진행한다. 각각 두가지 조건에서 얻은 최대값을 비교해서 최종 최대값을 선택하면 된다. 
    answer = max(tempMax, *max_element(dp.begin(), dp.end()));
    • 첫 번째 집을 털었다면 마지막 집은 털 수 없다.
      • 첫 번째 집 dp[0]이 고려할 수 있는 경우의 수는 1 가지 뿐. 첫 번째 집을 털었을 때. money[0] ⭕
      • 두 번째 집 dp[1]이 고려할 수 있는 경우의 수는 1 가지 뿐. 두 번째 집은 못 털 때. 따라서 두 번째 집 까지의 털 수 있는 돈의 최대값은 여전히 첫번째 집에서 털었던 money[0] 이다. dp[0] ⭕❌
      • 세 번째 집 dp[2]이 고려할 수 있는 경우의 수는 2 가지. 아래 두 경우 中 더 큰 최대값을 채택하면 바로 세 번째집 까지의 털 수 있는 돈의 최대값이 된다.
        • 세 번째 집을 털지 않는 경우 👉 dp[1] ⭕❌❌
        • 두 번째 집을 털지 않고 세 번째 집을 터는 경우 👉 dp[0] + money[2] ⭕❌⭕
        • 위 2 가지 경우 중 더 큰쪽을 세 번째집까지 얻을 수 있는 최대 값인 dp[2] 값으로 업뎃한다.
      • 네 번째 집 dp[3]이 고려할 수 있는 경우의 수는 2 가지. 아래 두 경우 中 더 큰 최대값을 채택하면 바로 네 번째집 까지의 털 수 있는 돈의 최대값이 된다.
        • 네 번째 집을 털지 않는 경우 👉 dp[2] (⭕❌❌와 ⭕❌⭕ 중 큰 것중에 선택했었다. dp[2] 값에 따라 ⭕❌❌❌ 혹은 ⭕❌⭕❌ 가 될 것이다.)
        • 세 번째 집을 털지 않고 네 번째 집을 터는 경우 👉 dp[1] + money[3] (⭕❌❌⭕)
        • 위 2 가지 경우 중 더 큰쪽을 네 번째집까지 얻을 수 있는 최대 값인 dp[3] 값으로 업뎃한다.
      • 마지막 번째 집이 고려할 수 있는 경우의 수는 1 가지 뿐. 첫번째 집이 털렸다고 가정하고 시작했기 때문에 마지막 집은 털리면 안된다. 따라서 dp[n - 2] 이다. 
        // 1. 첫 번째 집을 털었을 때(마지막 집은 털지 못한다.)의 전체
dp[0] = money[0];
dp[1] = dp[0];
for(int i = 2; i < money.size() - 1; i++)   // for문 에서 마지막 번째 집은 제외하고 돌린다. 물론 첫번째 두번째집도! 
    dp[i] = max(dp[i - 1], dp[i - 2] + money[i]);
dp.back() = dp[dp.size() - 2];
tempMax = *max_element(dp.begin(), dp.end());
    • 첫 번째 집을 털지 않았다면 마지막 집은 딱히 제한 없다.
      • 첫 번째 집 dp[0]이 고려할 수 있는 경우의 수는 1 가지 뿐. 첫 번째 집을 털지 않았을 때. dp[0] = 0 ❌
      • 두 번째 집 dp[1]이 고려할 수 있는 경우의 수는 2 가지. ❌❌는 0 이므로 두 번째 집을 터는 ❌⭕ 경우가 최대값이 된다. dp[1] = money[1]
      • 세 번째 집 dp[2]이 고려할 수 있는 경우의 수는 2 가지.
        • 세 번째 집을 털지 않는 경우 👉 dp[1] ❌⭕❌
        • 두 번째 집을 털지 않고 세 번째 집을 터는 경우 👉 dp[0] + money[2] ❌❌⭕
          • 실제로 두번째 집을 털기로 했건 안했건 그건 상관 없다. 그냥 여러 경우들 중에서 최대값을 선택하는 것 뿐이니까 ! dp[1]가 ❌⭕ 경우의 돈을 최대값으로 선택했다고 해서 두번째 집을 실제로 털었다는게 아니라 그냥 그 경우가 두번째집까지에선 가장 큰 돈을 가질 수 있는 경로였다는 것 뿐이다. 헷갈리지 말자! 세 번째 집까지 터는 모든 경우들 중 ❌❌⭕ 가 가장 많은 돈을 털 수 있다면 dp[1]과 전혀 상관 없이 ❌❌⭕로 털었을 때의 돈이 dp[2] 값으로 업뎃 되는 것이다. 
            // 2. 첫 번째 집을 털지 않았을 때의 전체
dp[0] = 0;
dp[1] = money[1];
for(int i = 2; i < money.size(); i++)
dp[i] = max(dp[i - 1], dp[i - 2] + money[i]);



🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)