[프로그래머스] 스티커 모으기(2)

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

[프로그래머스] 도둑질과 동일한 문제이다. 차이점이 있다면 N이 1인 경우 예외처리를 해줘야한다는 점이다.

코드

C++

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

int solution(vector<int> sticker){    
    int n = sticker.size();

    if(n == 1) return sticker[0];

    vector<vector<int>> dp(2, vector<int>(n, 0));
    dp[0][0] = 0;
    dp[1][0] = sticker[0];

    for (int i = 1; i < n; i++) {
        dp[0][i] = max(dp[0][i - 1], dp[0][i - 2] + sticker[i]);
        dp[1][i] = max(dp[1][i - 1], dp[1][i - 2] + sticker[i]);
    }
    return max(dp[0][n - 1], dp[1][n - 2]);
}

Python3

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

    dp = [[0] * n for _ in range(2)]
    dp[0][0] = 0
    dp[1][0] = sticker[0]

    for i in range(2):
        for j in range(1, n):
            dp[i][j] = max(dp[i][j - 1], dp[i][j - 2] + sticker[j])
    answer = max(dp[0][-1], dp[1][-2])
    return answer