4085 : 연속 K개 최대합 (슬라이딩)
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 6
•통과: 2
•만든사람: suakii
문제 설명
길이 $N$인 1차원 정수 배열에서 연속된 $K$개 원소의 합 중 최댓값과 그 최댓값을 만드는 첫 번째 원소의 시작 인덱스(1-indexed)를 구하는 프로그램을 작성하시오.
만약 합의 최댓값을 만족하는 구간이 여러 군데 존재한다면, 가장 앞서는(인덱스가 가장 작은) 구간을 선택한다.
[제약 조건]
• $1 \le N \le 1000$
• $1 \le K \le N$
• $-1000 \le (\text{각 원소}) \le 1000$
• 입력되는 모든 값은 정수
[제약 조건]
• $1 \le N \le 1000$
• $1 \le K \le N$
• $-1000 \le (\text{각 원소}) \le 1000$
• 입력되는 모든 값은 정수
입력 설명
첫째 줄에 배열의 크기 $N$과 연속 원소 개수 $K$가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
출력 설명
연속된 $K$개 원소의 최대합과 그 구간의 시작 인덱스를 공백으로 구분하여 출력한다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
1 2 3 4 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
12 3도움
슬라이딩 윈도우 방식으로 구현하면 효율적이다.