분 단위 예상 시청자 수 viewers에서 두 번의 방송 구간을 정해요. 각 구간은 정확히 width분의 연속 구간이며 앞 방송과 뒤 방송 사이에는 방송하지 않는 시간이 gap분 이상 있어야 해요. 두 구간의 예상 시청자 수 합을 가장 크게 만들어요.
solution(viewers, width, gap)이 [최대 합계, 앞 구간 시작 인덱스, 뒤 구간 시작 인덱스]를 반환하도록 작성해 주세요. 합계가 같으면 앞 시작이 작은 쌍, 그것도 같으면 뒤 시작이 작은 쌍을 골라요. 시작 인덱스는 0부터 세요. 두 구간을 배치할 수 없으면 [-1,-1,-1]이에요.
매개변수와 반환값
- 길이 n은 1
1,000, 시청자 수는 01,000이에요. - width는 1
n, gap은 0n이에요. gap=0이면 두 구간이 바로 붙어도 돼요. - 두 구간이 겹칠 수는 없어요. 앞 시작 a와 뒤 시작 b는
b >= a + width + gap을 만족해야 해요. - 반환 리스트 길이는 3이에요.
예시
viewers = [4, 1, 3, 2, 7, 1],width = 2,gap = 1이면 결과는[14, 0, 3]이에요.viewers = [2, 2, 2, 2, 2],width = 1,gap = 1이면 결과는[4, 0, 2]이에요.
실행용 입출력
첫 줄에 n width gap, 둘째 줄에 시청자 수 n개를 입력해요. 반환값 세 개를 한 줄에 출력해요.
예시 입력
6 2 1 4 1 3 2 7 1
예상 결과
14 0 3
예시 입력
5 1 1 2 2 2 2 2
예상 결과
4 0 2
핵심 개념
dp-1d: 뒤 구간을 오른쪽으로 옮길 때 연결 가능한 앞 구간이 하나씩 늘어요. 그동안 가능한 앞 구간 중 가장 좋은 합계·시작을 유지할 수 있어요.counting-aggregation: 누적합은 구간 합을 두 끝 값의 차이로 구해요. 각 방송의 길이와 사이 간격은 별도 조건이에요.array-1d:prefix[i]는 인덱스 i 직전까지의 합이에요. 리스트의[-1]은 마지막 항목을 뜻해 새 누적값을 만들 때 쓸 수 있어요.
튜플 (a,b)의 비교는 첫 항목을 먼저, 같으면 다음 항목을 비교해요. 합계가 같은 경우 작은 시작 쌍을 고르는 데 사용할 수 있어요. 리스트 컴프리헨션 [식 for i in range(...)]는 각 i에서 계산한 값을 모아요. return은 값을 반환하고 함수를 바로 끝내요.
입력 하네스의 input()은 한 줄의 문자열을 읽고, .split()은 공백으로 항목을 나눠요. map(int, ...)는 각 항목을 정수로 바꾸고 list(...)는 그 결과를 리스트로 모아요. range(n)은 0부터 n-1까지 반복해요. 하네스는 함수 호출을 위한 자체 연결이며 풀이의 반환 계약과 구분해요.