[코딩테스트 연습] 스티커 모으기(2)

 

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

---

DP 문제입니다. DP의 의미를 아래와 같이 정의합니다.

 

DP[N] = N번째 칸까지 스티커를 모았을 때 최대 점수

 

그러면 다음과 같은 점화식이 성립합니다.

DP[N] = max(DP[N-1], DP[N-2] + sticker[N])

 

단, 원형판이라는 특수한 조건이 있으므로 값을 한 번 더 분기해줘야 합니다.

첫 번째 칸의 스티커를 뗀 경우와 떼지 않은 경우입니다.

 

첫 번째 칸의 스티커를 뗀 경우라면 마지막 칸의 스티커는 떼면 안됩니다.

첫 번째 칸의 스티커를 떼지 않은 경우라면 마지막 칸의 스티커를 포함시킬 수 있습니다.

 

이렇게 BOTTOM-UP 형식으로 구해주면 됩니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter10.cc