https://programmers.co.kr/learn/courses/30/lessons/12971
dp문제였습니다.
풀이방법
greedy하게 띄엄띄엄 최대한으로 스티커를 떼어나면 최대일 것 같으나 그렇지 않습니다. 특정한 스티커가 점수가 나머지보다 월등히 높은 경우 그 스티커를 무조건 1개씩 건너뛰면서 떼어낼 경우 그 스티커를 떼지 못할 수 있습니다. 따라서 dp를 사용해야 합니다.
1. sticker의 size가 1인경우엔 바로 점수를 반환합니다.
2. 배열 d는 다음과 같습니다. d[i] = i번 스티커를 떼어내거나 떼어내지 않았을 때 얻을 수 있는 점수의 최댓값. 이를 점화식으로 표현한다면 아래와 같습니다.
d[i] = max(d[i-2] + sticker[i], d[i-1])
즉 d[i] = max(i번째 스티커를 뜯어내는 경우, i번째 스티커를 뜯지 않는경우)입니다. i번째 스티커를 뜯어내는 경우에는 i번째의 스티커 점수를 얻을 수 있습니다. 뜯어내지 않는 경우에는 규칙에 따라 i-1번째의 점수 최댓값을 그대로 가져오게 됩니다.
이 때 2가지 경우를 생각해야합니다.
2-1. 0번 스티커를 선택했을 때
마지막 스티커와 1번 스티커는 찢어지므로 뜯을 수 없습니다. 그러므로 d[0]과 d[1]는 sticker[0]이 됩니다. 그 후 i 는 2부터 size - 1미만까지 점화식을 따라 d를 갱신해줍니다. 그 후 마지막으로 갱신된 원소를 answer에 저장합니다.
2-2. 1번 스티커를 선택했을 때
0번 스티커와 2번 스티커는 뜯어낼 수 없습니다. 그러므로 d[0] = 0, d[1] = sticker[1]이 됩니다. 초기값을 갱신해준 후 i는 2부터 size미만까지 점화식을 따라 d를 갱신해줍니다. 그 후 마지막으로 갱신된 원소를 answer에 저장합니다.
3. answer를 반환해줍니다.
Code
#include <bits/stdc++.h>
using namespace std;
int solution(vector<int> sticker){
int answer = 0;
int size = sticker.size();
vector <int> d(size,0);
if (size == 1) return sticker[0];
d[0] = sticker[0];
d[1] = sticker[0];
for (int i = 2; i < size - 1; i++)
d[i] = max(d[i - 2] + sticker[i], d[i - 1]);
answer = d[size - 2];
d[0] = 0;
d[1] = sticker[1];
for (int i = 2; i < size; i++)
d[i] = max(d[i - 2] + sticker[i], d[i - 1]);
answer = max(answer,d[size-1]);
return answer;
}
'Algorithm > DP(Dynamic Programing)' 카테고리의 다른 글
(C++) - 백준(BOJ) 16195번 : 1, 2, 3 더하기 9 (0) | 2021.05.25 |
---|---|
(C++) - 백준(BOJ) 15592번 : 1, 2, 3 더하기 7 (0) | 2021.05.25 |
(C++) - 프로그래머스(연습문제) : 멀리 뛰기 (0) | 2021.05.18 |
(C++) - 백준(BOJ) 2096번 : 내려가기 (0) | 2021.05.11 |
(C++) - 백준(BOJ) 15988번 : 1, 2, 3 더하기 3 (0) | 2021.05.03 |