이번 문제는 프로그래머스의 레벨 3 스티커 모으기(2) 문제이다.
문제가 꽤 짧아 고르게 되었고, 차근차근 읽어보도록 하자.
원형으로 연결된 최대 100000개의 스티커가 주어진다.
이 때 스티커를 뜯으면 양 쪽의 스티커도 같이 뜯어지게 된다.
하지만 점수는 가운데에 있는 스티커만 계산되어 버린다.
이 때 최대로 얻을 수 있는 점수를 계산하라!
DP
문제가 굉장히 짧고 간단하다.
보았을 때 백준에서 풀었던 스티커 문제가 생각이 났다.
그래서 보자마자 동적 계획법을 이용해야 겠다고 생각했다.
좀 더 자세히 근거를 찾아 보자.
우선 문제의 요구사항이 최대 값을 구하는 것이다.
그리고 현재 스티커를 뜯을 지 말지 결정할 때의 판단기준을 보면?
이 때 까지 뜯어온 스티커들의 값과 형태를 보고 결정할 수 있다.
즉, 이전 단계의 최대를 보며 현재의 최대를 갱신하는 것.
동적 계획법의 Memoization 기법을 의미한다.
그럼 문제를 어떻게 풀 수 있을까?
조건 분석
가장 먼저 현재 스티커에서 참조할 수 있는 이전 스티커의 위치를 생각해보자.
곰곰히 생각해보았을 때, 현재 스티커로부터 3칸 이상 떨어지는 것은 낭비이다.
왜? 5 2 3 4 10이라는 스티커가 있을 때, 현재 10을 보고있다고 가정하자.
그럼 3칸 뒤인 5의 값을 굳이 참조할 필요가 있을까?
아니다. 5의 값을 참조하려면 3도 참조하는 것이 반드시 이득이다.
따라서, 3칸 이상으로 값을 참조하는 것은 낭비라고 생각한다.
이제 가장 큰 문제는 스티커가 원형이라는 점이다.
첫번째 스티커를 떼어버리면, 마지막 스티커를 뗄 수 없게 된다.
첫번째 스티커를 떼지 않으면, 마지막 스티커를 뗄 수 있다.
즉, 첫번째 스티커를 기준으로 경우를 나눠 풀어야 할 것 같다.
- 첫번째 스티커를 떼는 경우
dp[0] = sticker[0];
dp[1] = dp[0];
for (int i = 2; i < sticker.size() - 1; i++)
dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i]);
dp[sticker.size() - 1] = dp[sticker.size() - 2];
max_v = *max_element(dp, dp + sticker.size());
// 첫번째 스티커를 선택하는 경우첫번째 스티커를 떼버리면 두번째, 마지막 스티커는 뗄 수가 없다.
따라서 곧바로 dp[2]부터 시작을 하며, dp[size-2]까지 진행한다.
마지막 스티커는 뗄 수가 없으므로, 따로 dp[size-1] = dp[size-2]로 갱신한다.
즉, 마지막 전 스티커까지의 최대 값을 그대로 물려받는 것이다.
- 첫번째 스티커를 떼지 않는 경우
dp[0] = 0;
for (int i = 1; i < sticker.size(); i++)
dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i]);
answer = max(max_v, *max_element(dp, dp + sticker.size()));
// 첫 번째 스티커를 선택하지 않는 경우첫번째 스티커를 떼지 않으면, 두번째 스티커를 이제 뗄 수 있다.
즉 dp[1]``부터 갱신을 시작하면 된다는 말이다.
마지막 스티커도 뗄 수 있는 가능성이 생겨,dp[size-1]```까지 진행한다.
총 2번의 Memoization을 통해서 두 가지 경우의 최대 값을 갱신했다.
꽤 간단한 코드로 답을 구할 수 있었다.
요즘 코딩테스트에서 DP 문제가 심심찮게 보이고 있다.
구현과 DP에 대해서 좀 더 대비를 할 필요가 있어 보인다.