#1. 문제
#2. 풀이
1. DP(Dynamic Programming, 동적 계획법)
동적 계획법은 주어진 문제의 하위 문제를 재귀적으로 해결하고, 그 결과 값을 기억하는 것으로 중복 계산을 방지하여 효율적으로 최적 해를 찾아내는 알고리즘 디자인 기법 중 하나입니다.
2. DP는 점화식을 세우고, 기저 조건을 먼저 설정하는 것이 중요!
- 먼저, 원형 배열의 첫 번째 칸을 선택하는 경우, 그리고 마지막 칸을 선택하는 경우를 모두 고려해야 합니다. 일반적인 DP를 수행하는 것과 달리, 마지막 칸에 대한 경우가 첫 번째 칸의 경우의 수에 영향을 끼치기 때문입니다.
- 그리고, 점화식을 세웁니다. 현재 칸에 대하여 이전의 결과 값들이 영향을 끼치며 이를 점화식으로 작성하면, "dp [i] = max(dp [i-1], dp [i-2]+sticker [i]), if size > 2"가 됩니다. i 칸의 경우, i-1칸을 선택하는 경우와 i-1칸 선택 + i칸 선택의 경우를 비교하여 더 큰 값으로 설정됩니다
- 따라서, 첫 번째 DP는 첫 번째 칸을 선택했을 경우로 시작합니다. dp1의 0번(첫 번째 칸) 과 1번(두 번째 칸) 인덱스는 모두 sticker [0]으로 기저 조건을 설정해 줍니다. 첫 번째 칸 선택 시 두 번째 칸은 자동적으로 선택 불가능하여, dp1 [1]은 sticker [0]으로 설정합니다.
- 그리고, 두 번째 DP는 첫 번째 칸을 선택하지 않앗을 경우로 시작합니다. dp2의 0번은 0, 그리고 1번은 sticker [1]로 기저 조건을 설정해 줍니다.
- 마지막으로, dp1의 n-2번 인덱스의 결과 값(마지막 칸 직전 위치)과 dp2의 n-1번 인덱스의 결과 값(마지막 칸 위치)을 비교하고, 더 큰 값으로 결과 값을 출력해 줍니다.
#3. 코드
/*
@링크: https://school.programmers.co.kr/learn/courses/30/lessons/12971
@문제: 스티커 모으기(2)
@설명
1. DP
2. dp[i] = max(dp[i-1], dp[i-2] + sticker[i]), if sticker.size() > 2
3. 두 버전의 동적 프로그래밍
- 첫 번째 항목과 마지막 항목은 연결되어 있는 순환 구조
- 첫 번째 항목을 선택하고 진행하는 DP, 마지막 항목을 선택하고 진행하는 DP
- 첫 번재 DP의 최종 결과 값은 dp[sticker.size()-2]에 위치하고, 두 번째 DP의 것은 dp[sticker.size()-1]에 위치.
*/
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int solution(vector<int> sticker)
{
if(sticker.size() == 1) return sticker[0];
if(sticker.size() == 2) return max(sticker[0], sticker[1]);
//@첫 번째 스티커 선택
vector<int> dp1(sticker.size(), 0);
dp1[0] = sticker[0];
dp1[1] = sticker[0];
for(int i=2; i<sticker.size()-1; ++i)
{
dp1[i] = max(dp1[i-1], dp1[i-2] + sticker[i]);
}
//@마지막 스티커 선택
vector<int> dp2(sticker.size(), 0);
dp2[0] = 0;
dp2[1] = sticker[1];
for(int i=2; i<sticker.size(); ++i)
{
dp2[i] = max(dp2[i-1], dp2[i-2] + sticker[i]);
}
return max(dp1[sticker.size()-2], dp2[sticker.size()-1]);
}
'문제 풀이 > Programmers 문제 풀이' 카테고리의 다른 글
[Programmers, C++]#Level2_ 호텔 대실, substr, sort 알고리즘, 우선순위 큐, 최소 힙 우선순위 큐 (1) | 2024.10.03 |
---|---|
[Programmers, C++]#Level2_마법의 엘리베이터, 올림, 내림, 반올림, 10진수 자릿수 구분 (0) | 2024.09.24 |
[Programmers, C++]#Level2_최솟값 만들기, 우선순위 큐, 최소 힙, 최대 힙, 완전 이진 트리 (0) | 2024.09.20 |
[Programmers, C++]#Level2_올바른 괄호, 스택, stack (0) | 2024.09.12 |
[Programmers, C++]#Level2_최댓값과 최소값, stringstream, istringstream, sstream (0) | 2024.09.12 |