이 문제는 ¶
인기도:B(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:3(1~4)
About Chopsticks ¶
중국에서는 음식을 먹을 때 젓가락 두 개를 쓰지만, L씨는 조금 다르다. 그는 젓가락 세 개를 사용한다. 셋 중 하나는 긴 젓가락으로, 음식을 쿡 찍어먹기 위한 용도로 쓰인다. 두 개의 일반 젓가락의 길이는 최대한 비슷해야 하지만 나머지 하나는 무조건 제일 길기만 하면 된다. 길이가 각각 A, B, C(A<=B<=C)인 세 개의 젓가락이 있을 때 (A-B)^2을 계산하면 두 젓가락이 짝이 안 맞는 정도를 구할 수 있다.
L씨는 그의 생일 파티에 K명의 손님을 초대했는데, 그의 특이한 젓가락질 방법을 소개하고 싶어서 안달이 나 있다. 젓가락을 K+8세트(L씨 자신, 부인, 아들, 딸, 어머님, 아버님, 장모님, 장인어른, 그리고 K명의 손님)를 준비해야 한다. 하지만 L씨네 집에 있는 젓가락들 중에는 길이가 다른 것이 많다. 젓가락들의 길이가 주어졌을 때, 각 세트의 짝이 안 맞는 정도를 최소화하면서 K+8세트를 만들어내는 방법을 찾아야 한다.
Input ¶
첫째 줄에는 테스트 케이스의 개수를 나타내는 정수 T(1<=T<=20)가 입력된다. 각 테스트 케이스의 첫째줄에는 손님 수를 나타내는 정수(0<=K<=1,000)와 젓가락의 개수를 나타내는 정수 N(3K+24<=N<=5,000)이 입력된다. 그 밑으로는 각 젓가락의 길이를 나타내는 N개의 양의 정수 Li(1 <= Li <= 32,000)가 오름차순으로 입력된다.
output ¶
입력된 각 테스트 케이스에 대해 한 줄에 하나씩, 모든 젓가락 세트의 짝이 안 맞는 정도의 합이 가지는 최소 값을 출력한다.
Sample Input ¶
~cpp 1 1 40 1 8 10 16 19 22 27 33 36 40 47 52 56 61 63 71 72 75 81 81 84 88 96 98 103 110 113 118 124 128 129 134 134 139 148 157 157 160 162 164
Sample Output ¶
~cpp 23
Note ¶
위의 입력 예에 대해서 다음과 같은 식으로 젓가락 세트를 구성할 수 있다.
8,10,16 ; 19,22,27; 61,63,75; 71,72,88; 81,81,84; 96,98,103; 128,129,148; 134,134,139; 157,157,160
8,10,16 ; 19,22,27; 61,63,75; 71,72,88; 81,81,84; 96,98,103; 128,129,148; 134,134,139; 157,157,160
풀이 ¶
작성자 | 사용언어 | 개발시간 | 코드 |
문보창 | C++ | 4시간 | Chopsticks/문보창 |