[Programmers] (고득점KIT) DP - 도둑질

Sierra·2022년 2월 8일
0
post-thumbnail

문제 설명

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

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

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

제한사항

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

입출력 예

moneyreturn
[1, 2, 3, 1]4

Solution

#include <string>
#include <vector>
#define MAX 1000001
using namespace std;

int DP1[MAX];
int DP2[MAX];

int solution(vector<int> money) {
    DP1[0] = money[0];
    DP1[1] = money[0];
    DP2[1] = money[1];

    for(int i = 2; i < money.size()-1; i++){
        DP1[i] = max(DP1[i-1], DP1[i-2] + money[i]);
    }
    for(int i = 2; i < money.size(); i++){
        DP2[i] = max(DP2[i-1], DP2[i-2] + money[i]);
    }
    return max(DP1[money.size()-2], DP2[money.size()-1]);
}

첫 번째 집을 만약 털었다면? 아니면 털지 않았다면? 이 두가지 경우에 따라 다르게 판단해야 하는 문제였다.

우선 첫 번째 집을 털었다면 자연스럽게 마지막 집을 털지 못한다. 집이 원 형태로 배치되어있다 생각해보면 마지막 집은 첫 번째 집과 인접하기 때문에 털 수 없다.

두 번째 집 또한 마찬가지. 두 번째 집을 털었다면 마지막 집을 털 수 있다.

이 두가지 경우에 대해 다르게 생각해보면 금방 풀 수 있다.

DP[i] = MAX(DP[i-1], DP[i-2] + money[i]

두 경우 다 공통적인 점화식을 공유한다. 현재 입장에서 보았을 때 지금 위치에서 돈을 터는 것이 이득이냐, 아니냐를 구별해야 한다. 돈을 턴다면 두칸 전의 DP값과 현재 위치의 money값을 더해야 할 것이다.

어차피 DP 테이블이라는 게 계속해서 갱신 해 나가는 것이다. 모든 경우에 대해 무작정 for문을 돌리는 건 비효율 적이기에 계속 이런식으로 갱신해나가다 보면 각 경우의 마지막 위치에는 최대로 털었을 때 돈이 나온다.

바로 생각해내기는 분명 어려울 수 있다. DP라는 게 상당히 추상적으로 느껴지는 개념이기 때문이다. DP 특성상 한번 그 점화식을 찾아버리면 바로 풀어버리는 문제라 더욱 연습이 필요하고 경험이 필요하다 생각한다. 처음에 이 점화식을 바로 찾지 못해서 해멨는데 아주 약간만 생각을 바꾸면 한 방에 풀었을 문제였다.

profile
블로그 이전합니다 : https://swj-techblog.vercel.app/

0개의 댓글