문제
정올마을의 이장이 된 도훈이는, 마을의 한 도로에 가로등이 전혀 없다는 것을 알게 되었다.
이에 도훈이는 이 도로에 가로등을 설치하려고 한다.
정올마을 마을회관에 정리된 자료에 따르면, 이 도로는 총 N개의 구역으로 나누어져 있다.
또한 각 구역별로, 해당 구역을 사람들이 얼마나 많이 다니는지에 대한 수치인 구역 방문 횟수가 정리되어 있다.
도훈이는 가로등을 K만큼의 거리를 두고 설치하려고 하는데,
이 경우 가로등을 설치하는 방법은 총 K가지가 된다.
도훈이는 이 K가지의 경우 중에서, 가로등이 설치된 구역의 방문 횟수 총합이 최대가 되도록 가로등을 설치하려고 한다.
예를 들어 N=10 , K=3인 경우를 생각해보자.
|
구역 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
방문 횟수 |
10 |
8 |
2 |
1 |
5 |
3 |
6 |
11 |
5 |
6 |
이 경우 가로등을 설치하는 방법은 다음의 3가지 경우가 있다.
|
구역 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
방문 횟수 |
10 |
8 |
2 |
1 |
5 |
3 |
6 |
11 |
5 |
6 |
이 경우 방문 횟수의 총합은 10+1+6+6 = 23이 된다.
|
구역 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
방문 횟수 |
10 |
8 |
2 |
1 |
5 |
3 |
6 |
11 |
5 |
6 |
이 경우 방문 횟수의 총합은 8+5+11=24이다.
|
구역 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
방문 횟수 |
10 |
8 |
2 |
1 |
5 |
3 |
6 |
11 |
5 |
6 |
이 경우 방문 횟수의 총합은 2+3+5 = 10이다.
따라서 가로등을 설치해야 하는 구역은, 방문 횟수의 총합이 24로 가장 큰 구역 2, 5, 8이다.
각 구역별 방문 횟수가 주어질 때, 가로등을 설치해야 하는 구역의 번호를 모두 출력하는 프로그램을 작성하시오.
입력
첫 줄에 구역의 수인 N과, 가로등을 설치해야 하는 거리인 K가 주어진다.
둘째 줄에, N개의 각 구역에 대해서, 구역 별 왕래 횟수 a<sub>i</sub>가 순서대로, 공백을 사이에 두고 주어진다.
부분문제의 제약 형식
모든 부분문제에서 3≤N≤100 , 1≤K<N, 1≤a<sub>i</sub>≤100이다.
주어진 모든 수는 자연수이다.
부분문제 1) (총 5점) N=20 , K=5이며 a<sub>1</sub>+a<sub>6</sub>+a<sub>11</sub>+a<sub>16</sub> = A, a<sub>1</sub>+a<sub>2</sub>+…+a<sub>N</sub> = S라고 하자. 이 때, A > S-A를 만족한다.
부분문제 2) (총 10점) K=1을 만족한다.
부분문제 3) (총 25점) K=N-1이고, 첫 번째 구역에 가로등을 설치하는 경우는 답이 아니다.
부분문제 4) (총 30점) N은 K의 배수이다.
부분문제 5) (총 30점) 주어진 제약 조건외에 아무 제약조건이 없다.
출력
한 줄에, 가로등을 설치해야 하는 모든 구역 번호를 공백을 사이에 두고 출력한다.
만약 방문 횟수의 총합이 같은 경우가 여러 경우라면, 가장 맨 앞에 가로등을 설치해야 하는 구역의 번호가 가장 작은 경우를 출력한다.
예제 #1
10 3
10 8 2 1 5 3 6 11 5 6
2 5 8
예제 #2
10 3
10 8 2 1 5 3 6 10 5 6
1 4 7 10
로그인해야 코드를 작성할 수 있어요.