[프로그래머스/C++] 도둑질

-inn·2022년 5월 12일
0

프로그래머스

목록 보기
1/4
post-thumbnail

도둑질 문제 바로가기

문제 풀이 과정

  • money = [1, 2, 3, 4, 5]라고 가정하고 식 찾아보자.
  • dp[n] : n 번째 집까지 털었을 때, 최댓값
  1. 각 집을 털었을 때, 최댓값을 구해보자.

    dp[0] = 1

    dp[1] = 2 or 1

    dp[2] = 1+3 or 2 or 1

    dp[3] = 1+4 or 2+4 or 1+3 or 2 or 1

    dp[4] = 2+5 or 3+5 or 1+4 or 2+4 or 1+3 or 2 or 1

  1. 규칙을 찾아보자.

    dp[0] = 1 → money[0]

    dp[1] = 2 or 1 → max(money[0], money[1])

    dp[2] = 1+3 or 2 or 1 → max(dp[0]+money[2], dp[1])

    dp[3] = 1+4 or 2+4 or 1+3 or 2 or 1 → max(dp[1]+money[3], dp[2])

    dp[4] = 2+5 or 3+5 or 1+4 or 2+4 or 1+3 or 2 or 1 → 어 ? 규칙이 보이지 않는다.

➡️ 첫 번째 집과 마지막 집을 터는 경우를 나눠서 계산해야겠구나 ! 완전 독립적인 경우
  1. 모든 경우의 수 고려해서 코드를 짜보자.

    마지막 집을 포함하여 집을 터는 경우

    dp[0] = 0 → 0

    dp[1] = 2 → money[1]

    dp[2] = 3 or 2→ max(dp[0]+money[2], dp[1])

    dp[3] = 2+4 or 3 or 2→ max(dp[1]+money[3], dp[2])

    dp[4] = 2+5 or 3+5 or 2+4 or 3 or 2 → max(dp[2]+money[4], dp[3])

✅ dp[i] = max(dp[i-2]+money[i], dp[i-1])

단, 최종 정답은 첫번째 집을 포함해 터는 경우, 마지막 집을 포함해 터는 경우의 최댓값으로 계산해줘야 한다.

코드

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

int dp1[MAX], dp2[MAX];
int answer;

int solution(vector<int> money) {
    int houseNum = money.size();
    
    // 첫번째 집 포함 털기
    dp1[0] = money[0];
    dp1[1] = max(money[0], money[1]);
    for (int i = 2; i < houseNum-1; i++) {
        dp1[i] = max(dp1[i-2] + money[i], dp1[i-1]);
    }
    
    // 마지막 집 포함 털기
    dp2[1] = money[1];
    for (int i = 2; i < houseNum; i++) {
        dp2[i] = max(dp2[i-2] + money[i], dp2[i-1]);
    }
    
    answer = max(dp1[houseNum-2], dp2[houseNum-1]);
    return answer;
}
profile
☁️

0개의 댓글