부품 상자 골라내기
문제
한 물류 창고의 컨베이어 벨트 위에 부품 상자 N개가 일렬로 놓여 있다. 1번부터 N번까지의 각 상자에는 그 안에 담긴 부품의 개수가 적혀 있다.
벨트의 끝에는 상자에 담긴 부품을 둘로 나누어 두 대의 트럭에 똑같이 실어 주는 분배기가 달려 있다. 분배기는 부품의 개수가 짝수인 상자만 받아 준다. 부품의 개수가 홀수인 상자가 하나라도 들어오면 분배기는 그 자리에서 멈춘다.
작업자는 분배기가 멈추지 않도록, 벨트 위의 상자를 최대 K개까지 집어낼 수 있다. 상자를 집어내면 그 양옆에 있던 상자가 서로 붙게 된다.
작업자가 집어낼 상자를 잘 골랐을 때, 분배기가 멈추지 않고 연달아 받는 상자의 개수가 가장 많은 경우를 찾아보자. 이때 연달아 통과하는 상자의 최대 개수를 계산하는 프로그램을 작성하여라.
예를 들어 N=10개의 상자에 담긴 부품의 개수가 다음의 표와 같고, K=2라고 해보자.
| 위치 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 부품 개수 | 1 | 2 | 3 | 4 | 2 | 2 | 1 | 5 | 6 | 8 |
벨트의 어느 구간을 통째로 분배기에 넣을지 먼저 정하고, 그 구간 안에 섞여 있는 홀수 상자를 집어내면 된다. 구간 몇 가지를 놓고 견주어 보면 다음의 표와 같다.
| 넣을 구간 | 2번부터 7번까지 | 4번부터 10번까지 | 2번부터 10번까지 |
|---|---|---|---|
| 집어낼 홀수 상자 | 3번, 7번 | 7번, 8번 | 3번, 7번, 8번 |
| 집어낼 상자 수 | 2개 | 2개 | 3개 |
| 통과하는 상자 수 | 4개 | 5개 | 집어낼 수 없음 |
맨 오른쪽 구간은 집어내야 하는 상자가 3개라서 K=2를 넘는다. 그래서 쓸 수 없다. 4번부터 10번까지의 구간을 고르고 7번 상자와 8번 상자를 집어내면, 벨트 위에 남은 상자는 다음과 같다.
| 위치 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 부품 개수 | 1 | 2 | 3 | 4 | 2 | 2 | 6 | 8 |
남은 상자 가운데 4번 위치부터 8번 위치까지의 다섯 상자는 부품의 개수가 모두 짝수다. 그래서 분배기가 멈추지 않고 상자 다섯 개를 연달아 받는다. 집어낼 상자를 다르게 골라 보아도 여섯 개를 연달아 통과시킬 수는 없다. 따라서 이 경우의 정답은 5다.
입출력 예시
예시 1
입력
10 2 1 2 3 4 2 2 1 5 6 8
출력
5
예시 2
입력
3 1 996951714 384279646 173346001
출력
2
예시 3
입력
1 1 866420415
출력
0
입력 조건
가장 먼저 첫째 줄에 상자의 수 N과 집어낼 수 있는 상자의 최대 개수 K가 공백으로 구분되어 주어진다. N은 1 이상 1,000,000 이하의 자연수다. K는 1 이상 10,000 이하의 자연수이며, N보다 크지 않다.
이어서 둘째 줄에 1번 위치부터 N번 위치까지의 상자에 담긴 부품의 개수가 공백으로 구분되어 한 줄에 주어진다. 각 부품의 개수는 1 이상 1,000,000,000 이하의 자연수다.
입력 전체의 크기는 최대 약 3.9MB다. 한 줄에 수가 최대 100만 개 들어오므로, 입력을 줄 단위로 읽어서 공백으로 나누는 방식으로 처리해야 한다.
출력 조건
분배기를 연달아 통과하는 상자의 최대 개수를 첫째 줄에 출력한다. 통과시킬 수 있는 상자가 하나도 없는 경우에는 0을 출력한다.
요구사항
- 상자를 꼭 K개 집어내야 하는 것은 아닙니다. K개보다 적게 집어내도 되고, 하나도 집어내지 않아도 됩니다
- 상자를 집어내면 그 양옆의 상자가 서로 붙습니다
- 연달아 통과하는 상자의 개수만 세며, 집어낸 상자는 개수에 넣지 않습니다
- 부품의 개수가 짝수인 상자가 하나도 없으면 정답은 0입니다
- N이 최대 100만이므로 모든 구간을 하나씩 확인하면 시간이 모자랍니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
1 1 866420415
0
3 1 996951714 384279646 173346001
2
10 2 1 2 3 4 2 2 1 5 6 8
5
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.