99클럽 코테스터디 41일차 TIL 프로그래머스- 도둑질

도둑질

프로그래머스 Level 4 DP
문제링크

프로그래머스

 

문제 설명

원형의 형태로 집들이 위치해 있고, 연속된 두 집을 방문하지 않으면서 최대로 가질 수 있는 값을 구하는 문제

문제 풀이

Buttom-up 방식으로 풀이했다.

첫번째 집을 방문하냐 안하냐로 두개의 dp 로 나눠 진행했다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dp1[1000000 + 30];
int dp2[1000000 + 30];

int solution(vector<int> money)
{
    int answer = 0;

    dp1[0] = money[0];
    dp1[1] = money[0];

    dp2[0] = 0;
    dp2[1] = money[1];

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

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

    answer = *max(max_element(dp1, dp1+money.size()), max_element(dp1, dp2+money.size()));

    return answer;
}

Python 코드

def solution(money):
    if len(money) == 1:
        return money[0]

    dp1 = [0] * len(money)
    dp2 = [0] * len(money)

    dp1[0] = money[0]
    dp1[1] = money[0]

    dp2[0] = 0
    dp2[1] = money[1]

    for i in range(2, len(money) - 1):
        dp1[i] = max(dp1[i-2] + money[i], dp1[i-1])

    for i in range(2, len(money)):
        dp2[i] = max(dp2[i-2] + money[i], dp2[i-1])

    answer = max(max(dp1[:len(money)-1]), max(dp2))

    return answer

회고

프로그래머스의 스티커 모으기와 완전히 동일한 풀이로 통과 가능한 문제였다
스티커 모으기

프로그래머스