#032 · DP중간1차원 DP,인접 제약

전광판 광고 슬롯 편성

문제

당신은 도심 전광판의 광고 편성을 맡았습니다. 하루 방송은 여러 개의 광고 슬롯으로 나뉘어 있고, prices[i]는 i번 슬롯을 판매했을 때 얻는 수익(원)입니다.

전광판은 광고를 한 번 내보내면 화면 보정을 위해 바로 다음 슬롯을 반드시 비워야 합니다. 즉 인접한 두 슬롯을 동시에 판매할 수 없습니다. 떨어져 있는 슬롯은 몇 개든 판매할 수 있고, 아무 슬롯도 판매하지 않아도 됩니다.

슬롯별 수익 배열 prices가 주어질 때 얻을 수 있는 최대 총수익을 반환하는 solution(prices) 함수를 작성하세요.

예시

prices	결과
`[30, 90, 40, 70, 20]`	`160`
`[50, 20, 10, 60, 60]`	`120`
`[40, 10, 90, 10, 40, 90, 10]`	`220`
`[7, 7]`	`7`

예시 1 설명: 1번과 3번 슬롯을 팔아 90 + 70 = 160원입니다. 0·2·4번을 모두 팔면 30 + 40 + 20 = 90원이라 더 적습니다.

예시 2 설명: 0·2·4번 슬롯을 팔아 50 + 10 + 60 = 120원이 최대입니다. 3번과 4번은 인접하므로 함께 팔 수 없습니다.

예시 3 설명: 0·2·5번 슬롯을 팔아 40 + 90 + 90 = 220원입니다.

제약 조건

1 ≤ prices.length ≤ 100,000
0 ≤ prices[i] ≤ 1,000,000 (정수)
판매하는 슬롯 개수에는 제한이 없습니다(0개도 허용).

시간 복잡도 목표: O(n)

공간 복잡도 목표: O(1)

테스트 케이스

예시 1: 1·3번 슬롯 → 90+70

입력: prices = [30,90,40,70,20]

출력: 160

예시 2: 0·2·4번 슬롯 → 50+10+60

입력: prices = [50,20,10,60,60]

출력: 120

예시 3: 0·2·5번 슬롯 → 40+90+90

입력: prices = [40,10,90,10,40,90,10]

출력: 220

예시 4: 인접한 두 슬롯 중 하나만 판매

입력: prices = [7,7]

출력: 7

엣지: 슬롯이 하나뿐

입력: prices = [12]

출력: 12

엣지: 모든 슬롯 수익이 0

입력: prices = [0,0,0,0]

출력: 0

solution.ts

에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.