CodeDrive

문제:

당신은 유명 프로그래밍 대회인 KCPC(Korean Collegiate Programming Contest)에 참가하고 있다. 이 대회에서 총 k개의 문제를 풀게 되는데, 어떤 문제에 대한 풀이를 서버에 제출하면 그 문제에 대해 0점에서 100점 사이의 점수를 얻는다. 풀이를 제출한 팀의 ID, 문제 번호, 점수가 서버의 로그에 제출되는 시간 순서대로 저장된다. 한 문제에 대한 풀이를 여러 번 제출할 수 있는데, 그 중 최고 점수가 그 문제에 대한 최종 점수가 된다. (만약 어떤 문제에 대해 풀이를 한번도 제출하지 않았으면 그 문제에 대한 최종 점수는 0점이다.)

당신 팀의 최종 점수는 각 문제에 대해 받은 점수의 총합이고, 당신의 순위는 (당신 팀보다 높은 점수를 받은 팀의 수)+1 이다. 

점수가 동일한 팀이 여럿 있을 수 있는데, 그 경우에는 다음 규칙에 의해서 순위가 정해진다. 

1. 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다. 
2. 최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다. 

동시에 제출되는 풀이는 없고, 모든 팀이 적어도 한 번은 풀이를 제출한다고 가정하라. 

서버의 로그가 주어졌을 때, 당신 팀의 순위를 계산하는 프로그램을 작성하시오.

입력:

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 팀의 개수 n, 문제의 개수 k, 당신 팀의 ID t, 로그 엔트리의 개수 m을 나타내는 4 개의 정수가 주어진다. 여기서, 3 ≤ n, k ≤ 100, 1 ≤ t ≤ n, 3 ≤ m ≤ 10,000이다. 그 다음 m개의 줄에는 각 풀이에 대한 정보가 제출되는 순서대로 주어진다. 각 줄에는 팀 ID i, 문제 번호 j, 획득한 점수 s를 나타내는 세 개의 정수가 주어진다. 여기서 1 ≤ i ≤ n, 1 ≤ j ≤ k, 0 ≤ s ≤ 100이다. 

출력:

출력은 표준출력을 사용한다. 주어진 각 테스트 데이터에 대해 당신 팀의 순위를 한 줄에 출력하여야 한다

풀이방법:

 주어지는 로그 엔트리들을 팀 ID, 문제 번호대로 정리를 잘 하고, 주어진 조건에 따라서 정렬을 하면 되는 문제다. 따라서 입력을 받을 당시에 defaultdict을 사용하여 raw 데이터를 저장하고, 이 와 동시에 가장 큰 점수와 마지막 인덱스도 저장하도록 한다.

 raw 데이터들은 Counter를 통해 빈도를 계산하며 이를 통합하여 정렬하도록 한다.

문제링크:

https://www.acmicpc.net/problem/3758

문제:

화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.

1. 자주 나오는 단어일수록 앞에 배치한다.
2. 해당 단어의 길이가 길수록 앞에 배치한다.
3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다

 M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자.

입력:

첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으로 구분되어 주어진다. (1≤ N ≤100,000, 1≤ M ≤10)

둘째 줄부터 N+1번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 10을 넘지 않는다.

단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.

출력:

화은이의 단어장에 들어 있는 단어를 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.

풀이방법:

defaultdict을 사용해서 나오는 횟수를 카운팅하며 (key, value) 값을 조건에 맞게 정렬하고 출력하도록 한다.

시간 제한이 걸려 있는 문제이므로 일반 input 대신 sys.stdin.readline을 사용해야 하며, rstrip()으로 개행문자를 제거해 주도록 한다.

문제링크:

https://www.acmicpc.net/problem/20920

문제:

상근이는 수학시간에 딴 짓을 하다가 선생님께 걸렸다. 선생님은 상근이에게 이번 주말동안 반성하라며 엄청난 숙제를 내주었다.

선생님이 상근이에게 준 종이에는 숫자와 알파벳 소문자로 되어있는 글자가 N줄있다. 상근이는 여기서 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야한다. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다.

글자를 살펴보다가 숫자가 나오는 경우에는, 가능한 가장 큰 숫자를 찾아야 한다. 즉, 모든 숫자의 앞과 뒤에 문자가 있거나, 줄의 시작 또는 끝이어야 한다.

예를 들어, 01a2b3456cde478에서 숫자를 찾으면 1, 2, 3456, 478이다.

선생님이 준 종이의 내용이 주어졌을 때, 상근이의 숙제를 대신하는 프로그램을 작성하시오.

입력:

첫째 줄에 종이의 줄의 개수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개의 줄에는 각 줄의 내용이 주어진다. 각 줄은 최대 100글자이고, 항상 알파벳 소문자와 숫자로만 이루어져 있다.

출력:

종이에서 찾은 숫자의 개수를 M이라고 하면, 출력은 M줄로 이루어져야 한다. 각 줄에는 종이에서 찾은 숫자를 하나씩 출력해야 한다. 이때, 비내림차순으로 출력해야 한다. 비내림차순은 내림차순의 반대인 경우인데, 다음 수가 앞의 수보다 크거나 같은 경우를 말한다.

풀이방법:

 python의 isdigit 기능을 사용해서 숫자를 찾도록 한다. 숫자가 연속해서 나오는 경우에는 이어붙이고, 숫자가 아닌 경우에만 배열에 담도록한다. 그리고 맨 끝의 숫자(lo3za4)에서 4도 탐색하기 위해서 for 문이 끝나고 나서 숫자가 남아있다면 추가로 넣어주도록한다.

 이렇게 모든 문자열 탐색이 끝난 뒤에, 배열에 있는 모든 숫자를 int형으로 바꾼 뒤에 정렬을 하도록 한다. (01과 같은 것을 제거하기 위함)

문제링크:

https://www.acmicpc.net/problem/2870

문제:

위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다.

창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다.

만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.

이렇게 정렬하는 방법을 빈도 정렬이라고 한다.

수열이 주어졌을 때, 빈도 정렬을 하는 프로그램을 작성하시오.

입력:

첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000)

둘째 줄에 메시지 수열이 주어진다.

출력:

첫째 줄에 입력으로 주어진 수열을 빈도 정렬한 다음 출력한다.

풀이방법:

 python의 Counter는 편리하고 빠르게 개수를 세도록 지원한다. Counter가 가진 함수 중에서 most_common이 자주 등장하는 순서로 정렬을 하는데, 개수가 같은 요소는 처음 발견된 순서를 유지한다. 이 문제에서 요구하는 조건과 같기 때문에 이를 사용하여 개수를 집계하고, 정렬된 순서에 따라 출력을 하도록 한다.

문제링크:

https://www.acmicpc.net/problem/2910

문제:

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

풀이방법:

 우선 N개의 재료들을 오름차순으로 정렬하고, 첫 값(start)과 마지막 값(end)에 포인터를 할당한다. 그리고 해당 위치에 있는 값들을 더하면서 M이 되는지 확인하고, 만약 M보다 크다면 end의 값을 줄이고, M보다 작거나 같다면 start를 하나 늘리도록 한다. 이 과정을 start와 end가 같아질 때까지 반복하도록 한다.(같은 순간에 종료)

문제링크:

https://www.acmicpc.net/problem/1940

문제:

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 

입력:

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력:

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

풀이방법:

 이 문제를 해결하기 위해서 다음과 같은 하나의 가정을 하도록 한다. Sn을 n까지의 저울추를 더한 값이라고 하고, An을 저울추라고 하자. 그럼 Sn+2 <= A(n+1)가 될 때, Sn+1은 측정할 수 없는 최솟값이 된다. 이러한 가정이 가능한 이유는 Sn이 Sn까지 무게를 측정할 수 있다는 의미를 가지기 때문이다.

 따라서 오름차순으로 정렬한 뒤에 저울추를 하나씩 올리면서 가정에 도달할 때까지 반복하도록 한다.

문제링크:

https://www.acmicpc.net/problem/2437

문제:

아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.

각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.

• 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
• 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
• 조건 3: 박스들 중 일부만 배송할 수도 있다.

마을의 개수, 트럭의 용량, 박스 정보(보내는 마을번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 단, 받는 마을번호는 보내는 마을번호보다 항상 크다.

예를 들어, 트럭 용량이 40이고 보내는 박스들이 다음 표와 같다고 하자.

이들 박스에 대하여 다음과 같이 배송하는 방법을 고려해 보자.

(1) 1번 마을에 도착하면

• 다음과 같이 박스들을 트럭에 싣는다. (1번 마을에서 4번 마을로 보내는 박스는 30개 중 10개를 싣는다.)

(2) 2번 마을에 도착하면

• 트럭에 실려진 박스들 중 받는 마을번호가 2인 박스 10개를 내려 배송한다. (이때 트럭에 남아있는 박스는 30개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 40개가 된다.)

(3) 3번 마을에 도착하면

• 트럭에 실려진 박스들 중 받는 마을번호가 3인 박스 30개를 내려 배송한다. (이때 트럭에 남아있는 박스는 10개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 30개가 된다.)

(4) 4번 마을에 도착하면

• 받는 마을번호가 4인 박스 30개를 내려 배송한다

위와 같이 배송하면 배송한 전체 박스는 70개이다. 이는 배송할 수 있는 최대 박스 개수이다.

입력:

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다. 

출력:

트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.

풀이방법:

입력으로 들어오는 값들을 적절히 잘 정렬하는 것이 중요하다. 입력들을 시작하는 마을로 정렬하게 된다면 다음과 같은 문제가 발생할 수 있다.

C = 20

1 4 30

2 3 20

3 4 20

 이 경우에는 1번 마을에서 택배를 싣고 출발하지만, 중간의 마을에서는 택배를 싣지 못하게 된다. 하지만 이 케이스의 정답은 1번 마을에서는 택배를 적재하지 않고, 2번마을, 3번 마을에서 각각 20씩 싣는 것이 최대 박스 수를 얻을 수 있다. 

 따라서 시작하는 마을을 기준으로 정렬하는 것이 아닌 도착하는 마을을 기준으로 정렬을 하도록 한다. 그리고 각 마을마다 가능한 용량 C를 초기화하고, 한 박스를 적재할 때마다 감소시키며, 최대한 많은 박스를 싣도록 한다.

문제링크:

https://www.acmicpc.net/problem/8980

문제:

체조나 다이빙 등의 경기에서 일부 심판이 자기가 좋아하는 선수에게 높은 점수를, 싫어하는 선수에게 낮은 점수를 주는 경우가 종종 있었다. 따라서 심판들이 주는 점수의 평균점수를 선수에게 주게 되면 공정하지 않은 경우가 생길 수 있다. 이를 방지하기 위하여 절사평균이나 보정평균을 사용한다. 예를 들어 심사위원 일곱 명이 다음과 같이 점수를 주었다고 하자.

9.3, 9.5, 9.6, 9.8, 9.1, 5.0, 9.3

전체의 합이 61.6이 되므로 평균은 8.8이 된다. 이 평균점수는 한 심판이 다른 심판에 비하여 아주 낮은 점수인 5.0을 주어서 나온 결과로, 선수는 매우 불공정하다고 느낄 것이다.

위의 점수를 작은데서 큰 순서로 정렬하면 5.0, 9.1, 9.3, 9.3, 9.5, 9.6, 9.8 이 된다.

이때 절사평균(7, 2)는 정렬된 전체 점수 일곱 개 중 양쪽 끝에서 두 개씩을 제외하고 난 9.3, 9.3, 9.5의 평균인 9.37이 된다(소수점이하 셋째 자리에서 반올림). 또 보정평균(7, 2)는 정렬된 전체 점수 일곱 개 중 양쪽 끝에서 각각 두 개를, 남은 점수 중 가장 가까운 것으로 교체한 9.3, 9.3, 9.3, 9.3, 9.5, 9.5, 9.5의 평균으로 9.39가 된다(소수점이하 셋째 자리에서 반올림).

N개의 점수와 양쪽에서 제외하는 개수 K 값이 주어졌을 때 절사평균(N, K)와 보정평균(N, K)를 계산하는 프로그램을 작성하시오.

입력:

첫째 줄에 전체 점수의 개수 N과 제외되는 점수의 개수 K가 빈칸을 사이에 두고 주어진다. N은 3 이상 100,000 이하의 자연수이다. K는 0 이상 (N/2)-1 이하로 주어진다. 그 다음 N줄에는 각 심판의 점수가 한 줄에 하나씩 주어진다. 점수는 0 이상 10 이하의 실수로 소수점이하 첫째 자리까지 주어진다.

출력:

첫째 줄에 절사평균(N, K)를, 둘째 줄에 보정평균(N, K)를 각각 소수점이하 셋째 자리에서 반올림하여 둘째 자리까지 출력한다. 예를 들어 결과값이 9.667인 경우 9.67로, 5인 경우 5.00으로, 5.5인 경우에는 5.50으로 출력한다.

풀이방법:

 조건에 맞게 필요하지 않은 값을 제외하고 평균을 구하면 되는 문제지만, 부동 소수점을 고려해야 한다. 부동 소수점 문제는 컴퓨터가 float을 표현할 때 발생하는 것을 의미한다. 예를 들어 0.3이 입력으로 들어와서 a라는 변수에 저장한다고 해도, a에는 정확히 0.3의 값이 들어가는 것이 아니라 0.3000000000001과 같이 부정확하게 값을 가지게 된다. 따라서 이러한 값들이 누적되어 평균을 구하게 되면 원래 원하던 평균과 달라지게 된다. 따라서 이러한 문제를 해결할 수 있는 여러 가지 방법이 있다.

 일반적으로 float을 지수 부분, 가수 부분으로 나눌 수 있기 때문에 이를 사용하는 방법이 있고, Python에서 이러한 문제점을 해결하기 위해 Decimal이라는 라이브러리를 제공하기도 한다. 하지만 1e-8과 같이 아주 작은 수를 더해주면 해결되는 방법도 있다고 한다. 따라서 평균을 구할 때, 1e-8과 같은 작은 수를 더해 부동소수점 문제를 해결하도록 한다.

문제링크:

https://www.acmicpc.net/problem/6986

문제:

아래 <그림 1>과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다.

<그림 1>

점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 예를 들어, <그림 1>의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 그리고 2번 가로 점선을 따라 자르면 <그림 2>와 같이 여러 개의 종이 조각으로 나뉘게 된다. 이때 가장 큰 종이 조각의 넓이는 30㎠이다.

<그림 2>

입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램을 작성하시오.

입력:

첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다. 입력되는 두 숫자 사이에는 빈 칸이 하나씩 있다.

출력:

첫째 줄에 가장 큰 종이 조각의 넓이를 출력한다. 단, 넓이의 단위는 출력하지 않는다.

풀이방법:

 입력으로 받은 잘라야 하는 순서를 오름차순으로 정렬한 뒤, 이전 값과의 차이를 구하며 모든 종이 조각의 넓이를 구하고 가장 큰 종이 조각을 출력하면 된다.

문제링크:

https://www.acmicpc.net/problem/2628

ㅌ문제:

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력:

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

출력:

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

풀이방법:

 해당 문제는 N개의 센서가 있을 때, K개의 그룹으로 만드는 것이 목적이다. 따라서 다음과 같은 알고리즘 순서대로 진행한다.

1. 센서들을 오름차순으로 정렬한다.

2. 각 센서들간의 차이를 구한다.

3. 각 센서들간의 차이를 내림차순으로 정렬한다.

4. 앞에서 부터 K-1개를 제외한 나머지들을 다 합한다.

문제링크:

https://www.acmicpc.net/problem/2212