6087 : 자료구조 종합 2 (대회형)
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
자료구조 종합 2 (대회형)
슬라이딩 윈도우 최댓값의 합을 구하시오.
크기 K인 슬라이딩 윈도우가 배열을 왼쪽에서 오른쪽으로 이동하면서,
각 윈도우의 최댓값을 모두 더한 총합을 출력합니다.
효율적인 구현: 단조 덱(Monotonic Deque) $O(N)$
- 덱에 인덱스를 저장하며, 현재 원소보다 작거나 같은 값의 인덱스는 덱 뒤에서 제거
- 윈도우를 벗어난 인덱스는 덱 앞에서 제거
- 덱의 앞 인덱스가 해당 윈도우의 최댓값
시간복잡도: $O(N)$
[제약 조건]
• 명령 수 $N$: $1 \le N \le 10$ (정수)
• 각 연산에 사용되는 자료구조 원소 수 $n \le 100{,}000$
• 시간 제한에 주의하여 최적 자료구조를 선택해야 합니다.
슬라이딩 윈도우 최댓값의 합을 구하시오.
크기 K인 슬라이딩 윈도우가 배열을 왼쪽에서 오른쪽으로 이동하면서,
각 윈도우의 최댓값을 모두 더한 총합을 출력합니다.
효율적인 구현: 단조 덱(Monotonic Deque) $O(N)$
- 덱에 인덱스를 저장하며, 현재 원소보다 작거나 같은 값의 인덱스는 덱 뒤에서 제거
- 윈도우를 벗어난 인덱스는 덱 앞에서 제거
- 덱의 앞 인덱스가 해당 윈도우의 최댓값
시간복잡도: $O(N)$
[제약 조건]
• 명령 수 $N$: $1 \le N \le 10$ (정수)
• 각 연산에 사용되는 자료구조 원소 수 $n \le 100{,}000$
• 시간 제한에 주의하여 최적 자료구조를 선택해야 합니다.
입력 설명
첫째 줄에 배열 크기 N (1 ≤ N ≤ 100,000)과 윈도우 크기 K (1 ≤ K ≤ N)가 주어집니다.
둘째 줄에 N개의 정수가 주어집니다.
둘째 줄에 N개의 정수가 주어집니다.
출력 설명
모든 슬라이딩 윈도우의 최댓값의 합을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8 3
1 3 -1 -3 5 3 6 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
28