[프로그래머스 고득점 kit] 도둑질 c++ (dp)

문제 링크

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

프로그래머스

 

문제 설명

우선 해당 문제는 레벨4를 책정받았는데, 이것에 너무 홀려서 어렵게만 생각하지말자.

우선 '원형' 이라는 것을 배제하고 일열로 늘어 놓는다고 가정했을 때,  x번째 값을 선택한다면 x-1번째 값은 선택할 수 없다.

따라서, 'x-1번째 값을 선택하는 경우의 수'를 따지거나. 'x-2번째와 x번째를 선택하는 경우의 수' 이 두가지를 고려해서 dp를 설계하면 된다.

따라서, 아래와 같이 점화식을 만들 수 있다. 

 

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

 

이제 해당 문제가 '원형' 이라는 것을 고려해보자. 복잡하게 생각할 필요 없이, 크게 2가지 경우의 수로 나눌 수 있다.

 

1) 첫번째 값을 포함하고, 마지막 값은 포함 x ->  첫번째 값을 포함하지 않고, dp를 n번째 까지 고려하기

 

2) 마지막 값을 포함하고, 첫번째 값은 포함 x -> 첫번째 값을 포함하고, dp를 n-1번째까지 고려하기

 

위의 두가지 케이스로 나누어준다면, 원형이라는 특성을 무시할 수 있게된다. 

따라서, 2개의 dp 배열을 구성하여, 각각의 dp를 구하고, 둘 중 더 큰 값을 리턴하면 된다.

 

정답 코드

#include <string>
#include <vector>
#include<math.h>
#include<iostream>
using namespace std;
int with_first[1000001];
int with_last[1000001];
int solution(vector<int> money) {
    int siz=money.size();
    
    with_first[0]=money[0];
    with_first[1]=max(money[0],money[1]);
    
    with_last[0]=0; //처음꺼 포함 x 가정 
    with_last[1]=money[1];
    
    for(int i=2;i<siz;i++){
        //처음 값 선택, 마지막값 선택 x 
        with_first[i]=max(with_first[i-1],with_first[i-2]+money[i]);
        //마지막 값 선택, 처음값 선택 x 
        with_last[i]=max(with_last[i-1],with_last[i-2]+money[i]);
    }
    
    // 첫번째 값을 포함했기 때문에, 마지막 값은 무조건 포함 x 따라서 마지막 직전의 DP 사용
    //(마지막-2번째 값+ 마지막 값의 경우의 수 고려 x)
    int case1=with_first[siz-2];
    
    //마지막값을 포함했기에, 마지막 값의 dp 구한다.
    int case2=with_last[siz-1]; 
   return max(case1,case2);
}