줄의 양끝이 연결되면 기존 답이 깨질 수 있어요
앞에서 바로 이웃을 함께 고르지 않는 선형 DP를 풀었어요. 이번에는 위치들이 원형으로 이어져 처음과 마지막도 이웃이에요. {5,1,5}에서 줄이었다면 양끝 합 10이지만 원형에서는 둘을 함께 고를 수 없어요.
나머지 바로 이웃한 쌍의 제약은 같아요. 새로운 제약이 기존 계산의 어느 경계에 영향을 주는지 먼저 읽어요.
적어도 한쪽 끝을 제외하는 두 경우로 나눠요
양끝을 함께 고를 수 없으므로 유효 선택은 ‘마지막을 제외한 줄’ 또는 ‘처음을 제외한 줄’ 중 적어도 한쪽에 있어요. 양쪽 모두 제외한 선택은 두 경우에 겹쳐도 최대값 비교에는 문제가 없어요.
| values | 마지막 제외 | 처음 제외 |
|---|---|---|
| {5,1,5} | {5,1}의 답 5 | {1,5}의 답 5 |
| {2,7,4,6} | {2,7,4}의 답 7 | {7,4,6}의 답 13 |
원소 한 개에서 두 끝을 모두 제외해도 될까요? 원형에 다른 이웃이 없다고 정한 한 개의 경우를 따로 다뤄요. 제공 lineBest의 const 참조는 값을 복사하지 않고 읽는 방식이에요. 범위가 비면 합 0을 반환해요.
직접 풀어봐요
values는 원형 순서의 혜택이에요. 바로 이웃한 위치 둘은 함께 고를 수 없으며 처음과 마지막도 이웃이에요. 선택한 값 합의 최댓값을 반환해요. 아무것도 안 골라도 돼요. 길이 1은 자기 자신을 이웃으로 보지 않아 그 한 값을 고를 수 있어요.
길이는 0100, 원소는 01000이에요. 빈 vector의 답은 0이에요. 제공 lineBest는 닫힌 구간 left~right의 선형 비인접 최대 합을 반환해요. 실행용 입력은 n과 n개 값, 출력은 반환값이에요. 하네스가 입출력을 처리해요.
예시 1: values={2,7,4,6} → 13. 1·3번의 7과 6은 원형에서도 이웃이 아니라 함께 골라요.
예시 2: values={5,1,5} → 5. 양끝 5 두 개는 이웃이라 하나만 골라요.
예시 입력
4 2 7 4 6
예상 결과
13
예시 입력
3 5 1 5
예상 결과
5
핵심 개념
dp-1d: 원형의 양끝 제약을 두 선형 경우로 나눠요.