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

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

프로그래머스

 

 

첫번째 스티커를 포함한 경우 / 포함하지 않은 경우로 나누고 dp로 풀었다.

 

1. dp[i][0]

첫 번째 포함했을 때의 i번째 스티커까지 최댓값 
dp[i][0] = max(dp[i-2][0]+sticker[i], dp[i-1][0]) 

• dp[i-2][0] + sticker[i]: i-2 번째를 포함하고, i-1는 포함하지 않고 (찢어져서 못씀), i를 포함한 경우 
• dp[i-1][0] : i-1를 포함하고, i번째 포함하지 않는 경우

이때 첫 번째 스티커를 포함한 경우에는, 마지막 스티커는 포함 불가하므로 i = n-1 제외

 

2. dp[i][1]

첫 번째 포함 안했을 때의 i번째 스티커까지 최댓값 

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

• dp[i-2][1] + sticker[i]: i-2 번째를 포함하고, i-1는 포함하지 않고 (찢어져서 못씀), i를 포함한 경우 
• dp[i-1][1] : i-1를 포함하고, i번째 포함하지 않는 경우

 

dp[i][0] != i번째를 포함했을 때 최댓값, dp[i][1] != i번째를 포함 안했을 때 최댓값

1차원 벡터 dp1, dp2를 2차원 벡터에 넣어서 dp[i][0], dp[i][1] 로 저장한 형태

 

 

⭐️ input 갯수가 10만까지였는데, vector를 쓰니 효율성에서 걸렸다. 이때 int 배열로 바꿔주니 해결됐다 ! 

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

using namespace std;

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

    if (n == 1) {
        return sticker[0];
    }
    int dp[n][2];
    memset(dp, 0, sizeof(dp));

    dp[0][0] = sticker[0]; // dp[i][0] = 1번째 스티커 포함
    dp[1][0] = sticker[0];

    dp[0][1] = 0; // dp[i][1] = 1번째 스티커 포함 X
    dp[1][1] = sticker[1];

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

    return max(dp[n - 2][0], dp[n - 1][1]);
}