[프로그래머스] Level 4. 도둑질

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

프로그래머스

 

이전에 레벨3에서 똑같은?문제를 풀었던것같아서 쉽게풀었다. 그래도 첫 Level 4다 ㅎㅎ

 

F(N) 을 생각해보면, n번째를 선택하는경우와 선택하지 않는경우 2가지가있다.

만약 선택한다면, n-1번째는 선택되지 않아야한다. n-1이 선택되지않으면서 최대값을 유지하는것은 F(n-2) 이므로,

n번째를 선택하는 경우 => F(n-2) + money[n] 

n번째를 선택하지 않을 경우는 F(n-1) 과 동일할것이다.

 

따라서 F(n) = max (F(n-1), F(n-2)+money[n]) 이라는 식이 나온다.

 

 

여기서  또 주의할 점은, 원형으로 되어있어서 배열의 마지막과 첫번째가 인접해있다는것이다. 

첫번째 집을 선택하는 경우와 선택하지 않는경우 두가지를 구해서, 둘중 max를 선택한다.

answerA 는 첫번째 집을 선택했기 때문에 answerA[0] = money[0] 이다. 마지막집은 선택되면 안되기때문에 범위를 money.size()보다 하나 작게 설정했다.

 

answerB는 첫번째 집을 선택하지 않는 경우로, answerB[0] = 0 이다. 마지막집은 선택될수 있으므로 범위도 money.size()까지 설정한다.

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> money) {
    
    vector<int> answerA(money.size(),0);
    vector<int> answerB(money.size(),0);
    
    answerA[0] = money[0];
    answerA[1] = max(money[0], money[1]);
    
    for(int i = 2; i<money.size()-1; i++){ 
        answerA[i]= max(answerA[i-2]+money[i] , answerA[i-1]); //0을 선택했으니 마지막꺼 선택불가능
    }
    
    answerB[0] = 0; //첫번째꺼 선택하지않음
    answerB[1] = money[1]; 
    
    for(int i = 2; i<money.size(); i++){ 
        answerB[i]= max(answerB[i-2]+money[i] , answerB[i-1]); //0을 선택X. 마지막꺼 선택불가능
    }
    return  max(answerA[money.size()-2],answerB[money.size()-1]);
}

 

 

기억속에 있어서 쉽게 풀었다했는데,

https://journal-devchop.tistory.com/128

[프로그래머스] Level 3. 스티커 모으기

 

이문제와 같은문제이다.