원형 진열대에서 떼어낼 수 있는 최대 스티커 점수
자바스크립트 코딩테스트 문제로 circular-dp 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
원형으로 놓인 스티커에서 이웃한 두 장을 함께 떼지 못할 때 얻을 수 있는 최대 점수를 구하는 문제입니다.
문제 설명
정수 배열 stickers가 주어집니다.
각 원소는 원형 진열대에 붙어 있는 스티커의 점수입니다.
스티커를 몇 장 떼어 점수를 얻으려 합니다. 단, 서로 이웃한 두 스티커는 동시에 떼어낼 수 없습니다. 원형 진열대이므로 첫 번째 스티커와 마지막 스티커도 서로 이웃입니다.
얻을 수 있는 점수의 최댓값을 반환하는 maxStickerScoreOnCircle 함수를 작성하세요.
제한사항
stickers의 길이는1이상100,000이하입니다.stickers[i]는0이상10,000이하의 정수입니다.- 스티커를 하나도 떼지 않아도 되지만, 최댓값을 만드는 선택을 반환하면 됩니다.
예시
- 입력:
stickers = [14, 6, 5, 11, 3, 9, 2, 10]→ 출력:36 - 입력:
stickers = [5, 1, 1, 5]→ 출력:6 - 입력:
stickers = [8]→ 출력:8 - 입력:
stickers = [4, 10]→ 출력:10
힌트
- 선형 배열에서 이웃한 값을 동시에 고르지 않는 최대 합 문제를 떠올려 보세요.
- 여기서는 첫 번째와 마지막도 이웃이므로, 두 칸을 동시에 고르는 경우만 특별히 막아야 합니다.
첫 칸을 쓰는 경우와첫 칸을 안 쓰는 경우로 나누면 원형 조건이 사라집니다.
해설
핵심은 원형 제약을 선형 DP 두 번으로 바꾸는 것입니다.
선형 배열이라면 각 위치에서
- 현재 스티커를 떼지 않는 경우
- 현재 스티커를 떼는 경우 를 비교하는 전형적인 DP로 풀 수 있습니다.
하지만 이 문제는 원형이라서 첫 번째와 마지막 스티커를 동시에 고를 수 없습니다. 그래서 아래 두 경우로 나눕니다.
- 마지막 스티커를 제외하고
0 ~ n-2구간만 본다.- 이 경우 첫 번째 스티커를 고를 수 있습니다.
- 첫 번째 스티커를 제외하고
1 ~ n-1구간만 본다.- 이 경우 마지막 스티커를 고를 수 있습니다.
이 두 선형 문제의 정답 중 더 큰 값이 전체 정답입니다.
선형 DP는 다음처럼 진행할 수 있습니다.
take: 현재 칸을 떼는 경우의 최대 점수skip: 현재 칸을 떼지 않는 경우의 최대 점수
혹은 더 간단히,
dp[i] = max(dp[i - 1], dp[i - 2] + stickers[i])형태로 볼 수도 있습니다.
예를 들어 stickers = [5, 1, 1, 5]라면
- 마지막 제외:
[5, 1, 1]→ 최댓값6 - 첫 칸 제외:
[1, 1, 5]→ 최댓값6
원형 전체에서 5 + 5 = 10은 불가능합니다. 양 끝이 이웃이기 때문입니다.
그래서 정답은 6입니다.
이 방법은 배열을 길이 n만큼 두 번만 훑으므로 시간 복잡도는 O(n), 추가 공간은 O(1)까지 줄일 수 있습니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.