문제 1011 · 기초 3
가장 붐빈 K일
누적합 · 슬라이딩 윈도우 · 배열
테스트별 제한 1500ms · 브라우저 채점
문제
개발 블로그의 N일 동안 날마다 방문자 수가 기록되어 있다. 연속한 K일을 골라 방문자 수를 더했을 때 합이 가장 큰 구간을 찾으려 한다. 합이 가장 큰 구간의 시작일(1일째부터 센다)과 그 합을 구하라. 합이 가장 큰 구간이 여러 개면 가장 이른 시작일을 고른다.
입력
첫째 줄에 N 과 K 가 주어진다. (1 ≤ K ≤ N ≤ 50,000) 둘째 줄에 날마다의 방문자 수 N개가 공백으로 구분되어 주어진다. 방문자 수는 0 이상 100,000 이하의 정수다.
출력
합이 가장 큰 구간의 시작일과 합을 공백으로 구분해 출력한다.
예제 입력 1
7 3 120 80 200 150 90 210 50
예제 출력 1
4 450
예제 입력 2
5 2 10 20 20 10 30
예제 출력 2
2 40
힌트 펼치기
- 구간을 하루 옮기면 합은 '새로 들어온 날 − 빠진 날' 만큼만 바뀐다. 매번 K개를 다시 더하면 너무 느리다.
- 최댓값을 갱신할 때 '같으면 바꾸지 않는다' 로 두면 가장 이른 시작일이 남는다.
관련 장
풀이 작성
코드는 서버로 전송하지 않습니다. 테스트가 공개되는 연습용 채점으로, 대회·인증용이 아닙니다.
풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.
로그인 여부와 관계없이 이 브라우저에만 최근 제출 50개를 저장합니다.