도둑질 - 프로그래머스

문제

문제 난이도 : 프로그래머스 4단계

문제 분류 : 다이나믹 프로그래밍

 

문제 리뷰

환형이라서 헛짓거리 하다가...

1시간 20분 만에 아이디어 떠올리고 호다닥 풀었다...

그래도 조금은 성장했나보다 ㅠ

문제 소스 코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(vector<int> money) {
    int answer = 0;
    int n = money.size();
    int DP1[1000001];
    int DP2[1000001];
    // DP[1] = 1
    // DP[2] = 2
    // DP[3] = 3
    // DP[4] = 4
    // DP[5] = 8
    // 1 2 3 1 5 
    
    // 1 2 3 1
    // 2 3 1 5
    DP1[0] = 0;
    DP2[0] = 0;
    DP1[1] = money[0];
    DP2[1] = money[1];
    
    for(int i = 2; i <= n; i++){
        DP1[i] = max(DP1[i - 1] , money[i-1] + DP1[i-2]);
        DP2[i] = max(DP2[i - 1] , money[i] + DP2[i-2]);
    }
    //cout << DP1[n-1];
    //cout << DP2[n-1];
    return max(DP1[n-1], DP2[n-1]);
}