야외 행사장에 기둥이 일렬로 박혀 있습니다. heights[i]는 i번 기둥의 높이이고,
이웃한 기둥끼리의 간격은 모두 1로 같습니다.
기둥 두 개를 골라 그 사이에 차양막을 팽팽하게 걸면 아래와 같은 넓이의 그늘이 생깁니다.
그늘 넓이 = (두 기둥의 인덱스 차) × (두 기둥 높이 중 더 낮은 쪽)준비된 차양막 자재로는 인덱스 차가 D를 넘는 기둥 쌍은 연결할 수 없습니다.
그늘 넓이가 가장 큰 기둥 쌍의 인덱스를 [왼쪽 기둥, 오른쪽 기둥] 형태로 반환하는
solution(heights, D) 함수를 작성하세요.
넓이가 같은 쌍이 여럿이면 왼쪽 기둥의 인덱스가 더 작은 쌍, 그래도 같으면
오른쪽 기둥의 인덱스가 더 작은 쌍 을 반환합니다.
heights=[3,9,4,2,6,5], D=3 → [1,4]
1번(9)과 4번(6)을 잇는다. 넓이는 (4-1) × min(9,6) = 3 × 6 = 18로 최대다.
heights=[3,9,4,2,6,5], D=1 → [4,5]
이웃한 기둥만 이을 수 있고, 그중 (6,5) 쌍의 넓이 1 × 5 = 5가 가장 크다.
heights=[10,1,1,1,10], D=3 → [0,3]
양 끝(넓이 40)은 인덱스 차가 4라서 자재가 모자란다.
가능한 쌍 중 넓이 3이 최대이고, (0,3)과 (1,4)가 동점이라 왼쪽이 앞선 (0,3)을 고른다.
heights=[5,5,5], D=2 → [0,2]시간 복잡도 목표: O(N × D)
▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.