[C++로 풀이] 스티커 모으기2 (DP)⭐⭐⭐

Date: 2021.03.07 Updated: 2021.03.07

카테고리: Programmers

📌 스티커 모으기(2)

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이

✈ 1 차 풀이 ❌

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

int solution(vector<int> sticker)
{
    int answer = 0;
    int sum = 0;
    
    if (sticker.size() == 1)
        return sticker[0];
    
    if (sticker.size() % 2 == 0){ // 짝수일 때
        for(int i = 0; i < 2; ++i){ // 짝수의 경우 예제 1로 예를 들면 [14,5,3,2] 혹은 [6,11,9,10] 둘중에 하나가 된다고 생각했었다.
            for(int j = i; j < sticker.size(); j += 2)
                sum += sticker[j];
            answer = max(answer, sum);
            sum = 0;
        }
    }
    else{ // 홀 수 일 때
        for(int i = 0; i < sticker.size(); ++i){ // 홀수의 경우 예제 2로 예를 들면 [1,2], [3,5], [2,4] [5,1] [4,3] 이렇게 나눌수 있다고 생각했었다. 
            int count = 0;
            for(int j = i; ; j += 2) {
                if (count == sticker.size() / 2)
                    break;
                if (j >= sticker.size())
                    j = j % sticker.size();
                sum += sticker[j];
                count++;
            }
            answer = max(answer, sum);
            sum = 0;
        }
    }
    
    return answer;
}

예제 테스트케이스는 다 맞는데.. 실행 및 채점하면 모든 케이스 다 틀리는 풀이이다. ㅎㅎ.. 다이나믹 프로그래밍 문제인지 아예 감을 못 잡았다. 나에게 가장 낯설고 문제 봤을 때 어떤 알고리즘을 써야하는지 알아차리기 어려운 알고리즘이 바로 다이나믹 프로그래밍 문제인 것 같다. 😭 아직 멀었네.. 많이 풀어봐야할 듯 싶다. 근데 프로그래머스에서 DP 문제 풀 때 아래와 같은 경우가 많았던 것 같다. ㅋㅋ

혹시 DP 문제는 아닐까 하고 의심 해야 하는 경우
- 전에 이미 구해서 저장해놓은 값들을 바탕으로 현재의 값을 구하는 점화식을 세울 수 있을 때
- 최대값, 최소값 같은 최적해를 구해야 할 때
  - 모든 원소들마다 그때까지 선택한 최적해를 구할 수 있을 때
- 입력 크기가 엄청 클 때
- 예제 테스트케이스는 다 맞는데 실행하면 많이 틀릴 때
  - ㅋㅋ 내가 생각해도 어이없지만.. 프로그래머스에서 DP 유형 문제를 DP 적용 안하고 풀었을 때 대부분 이랬다..

✈ 2 차 풀이 ⭕ (다이나믹 프로그래밍)

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

int solution(vector<int> sticker)
{
    int answer = 0;
    int tempMax = 0;
    int n = sticker.size();
    vector<int> dp(sticker.size());  
    
    if (sticker.size() == 1)
        return sticker[0];
    
    dp[0] = sticker[0];
    dp[1] = dp[0];
    for(int i = 2; i < n - 1; i++)
        dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i]);
    dp[n - 1] = dp[n - 2];
    tempMax = *max_element(dp.begin(), dp.end());
    
    dp[0] = 0;
    for(int i = 1; i < n; i++)
        dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i]);
    
    answer = max(tempMax, *max_element(dp.begin(), dp.end()));
    
    return answer;
}

DP 유형의 문제임을 깨닫고나니 예전에 고득점 키트에서 풀었던 도둑질 문제와 인접한, 이웃한 원소는 배제해야 하고 순환한다는 점에서 매우 유사하다는 것을 떠올렸다. 스티커 배열 사이즈가 1 이면 첫번째 원소를 리턴해준다는 것을 추가해준 것 빼고는 도둑질 문제 풀이와 완전히 동일하다!

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

점화식이 이렇기에 dp[0], dp[1] 은 피보나치 수열에서 a1, a2 값이 미리 정해져있듯, 미리 정해놔야 한다.

점화식 👉 dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i])
- dp[i] : sticker[0] 스티커부터 sticker[i] 스티커까지의 모든 경우를 고려해서 누적해온 여태까지 구할 수 있는 합의 최대값. 즉, 첫번째 스티커부터 현재 스티커까지 고려하는 모든 케이스들 중에 가장 합이 최대가 될 때의 값.
  - “sticker[i]스티커를 뜯는 경우 Vs 뜯지 않는 경우” 둘 中 하나에서 최대 값을 선택한다.”
    - dp[i - 1]
      - sticker[i] 스티커를 뜯지 않기로 결정한 경우.
        
        sticker[0] 스티커부터 sticker[i - 1] 스티커까지의 모든 경우를 고려해서 누적해온 합의 최대값을 그대로 물려 받는다.
    - dp[i - 2] + sticker[i]
      - sticker[i] 스티커를 뜯기로 결정한 경우.
        
        인접한 sticker[i - 1]은 뜯지 못하기 때문에 sticker[i - 2] 스티커까지의 모든 경우를 고려해서 누적해온 합의 최대값에서 현재의 스티커 값인 sticker[i]를 더하면 된다.
    - 위 두 값에서 더 큰 것을 고르면 그게 바로 sticker[i] 스티커까지의 여태까지의 모든 케이스들 중에서 가장 합이 최대인 경우 값이 된다.

같은 점화식이지만 첫 번째 스티커를 뜰었냐 안 뜯었냐로 전체 dp 값이 달라지기 때문에 dp 구하는 것을 2 번 진행한다
- 첫 번째 스티커를 뜯은 경우의 점화식
  - i = 0 일 때 dp[0] = sticker[0] (첫 번째 스티커를 뜯었으므로)
  - i = 1 일 때 dp[1] = dp[0] (첫 번째 스티커를 뜯지 않았으므로 두번째 스티커까지의 최대합은 첫번째 스티커 값이 된다.)
  - 2 <= i <= n - 2 일 때 dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i])
  - i == n - 1 일 때 dp[n - 1] = dp[n - 2] (마지막 스티커는 뜯지 못 해야 하므로)
- 첫 번재 스티커를 뜯지 않은 경우의 dp
  - i = 0 일 때 dp[0] = 0 (첫 번째 스티커를 뜯지 않았으므로 첫번째 스티커까지의 최대합은 0이 된다.)
  - i >= 1 일 때 dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i])

마지막 스티커와 두 번째 스티커는 첫 번째 스티커를 동시에 뜯을 수는 없기 때문에 두 가지 경우로 나누어야 한다.

뜯어낸 스티커 양쪽에 인접한 두 스티커는 사용하지 못하기 때문에 첫 번째 스티커를 뜯었냐 안뜯었냐 로
- 모든 원소의 DP 값(여기까지 선택했을 때 합의 최대값)이 달라질 수 있다.
- 마지막 스티커를 뜯을 수 있는 경우 없는 경우로 갈리게 된다. (마지막 스티커는 첫 번째 스티커와 인접하기 때문이다.)
- 두 번째 스티커를 뜯을 수 있는 경우 없는 경우로 갈리게 된다. (두번째 스티커는 첫 번째 스티커와 인접하기 때문이다.)

🔥 첫 번째 스티커를 뜯은 경우

    dp[0] = sticker[0];
    dp[1] = dp[0];
    for(int i = 2; i < n - 1; i++)
        dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i]);
    dp[n - 1] = dp[n - 2];
    tempMax = *max_element(dp.begin(), dp.end());

첫 번재 스티커를 뜯은 여부와 상관 없이 다른 스티커들은 뜯을지 말지 선택지가 있지만 첫 번재 스티커를 뜯는다면 두번째 스티커와 마지막 스티커는 무조건 뜯을 수 없다. 즉, 마지막 스티커는 무조건 dp[i - 2] + sticker[n - 1] 가 최대합으로 선택될 수 없다는 이야기이다. 첫 번째 스티커를 뜯은 경우 마지막 스티커의 점화식은 dp[n - 1] = dp[n - 2] 가 되야 한다. 고려할 수 있는 경우가 한 가지밖에 없기 때문에!

첫 번째 스티커를 뜯는 다면 dp[0] = sticker[0]
- 두 번째 스티커는 무조건 뜯을 수 없다. 뜯는 선택지는 고려되지 않는다. dp[1] = dp[0]
- 마지막 스터키는 무조건 뜯을 수 없다. 뜯는 선택지는 고려되지 않는다. dp[n - 1] = dp[n - 2]
- 그외의 스티커는 해당 스티커를 뜯을지 혹은 말지에 대한 선택지가 주어진다. dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i])

🔥 첫 번째 스티커를 뜯지 않은 경우

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

첫 번째 스티커를 뜯지 않는다면 두번째, 마지막 스티커도 다른 스티커들처럼 뜯을지 말지 선택지가 생긴다.

첫 번째 스티커를 뜯지 않는 다면 dp[0] = 0
- 그외의 스티커는 해당 스티커를 뜯을지 혹은 말지에 대한 선택지가 주어진다. dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i])

두 번째 스티커도 뜯을지 말지로 선택지가 생기기 때문에 (사실 첫번재 스티커를 뜯지 않았기 때문에 무조건 두번째 스티커는 뜯는게 답이지만) dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i]) 점화식에 해당될 수도 있지만 두번째 스티커는 i = 1 이기에 dp[i - 2]에서 런타임 에러가 발생할 수 있다. 근데 max 함수에서 이를 알아서 처리해주는건지 에러가 딱히 발생하지 않길래 위와 같이 코딩하였다.

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

정확히는 이게 맞을 것 같다.

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️