pascal 1461번 도서관 (백준)

var n,m,i,j,x,g:int64;a:array[0..9999]of integer;
begin
readln(n,m); //입력
g:=n div 2;n-=1; //shell sort 준비
for i:=0 to n do read(a[i]); //책들의 위치들을 배열로 입력받음
while 1=1 do begin //shell sort : 오름차순 정렬
if (g mod 2)=0 then g+=1;
for i:=g to n do begin
j:=i-g;x:=a[i];
while j>=0 do begin
if a[j]>x then a[j+g]:=a[j] else break;j-=g;
end;
a[j+g]:=x;
end;
if g=1 then break;
g:= g div 2;
end;
x:=0;n+=1;i:=0; //음수값부터 이동거리 계산하기
while i<n do begin
if a[i]>0 then break else begin x+=a[i]*(-2);i+=m;end; //음수값이라면 *2 후 +m, 양수값이라면 종료
end;
i:=n-1; //인덱스를 배열의 맨 마지막으로
while i>=0 do begin //양수값의 이동거리 계산하기
if a[i]<0 then break else begin x+=a[i]*2;i-=m;end; //양수값이라면 *2후 +m, 음수값이라면 종료
end;
if a[n-1]>-a[0] then x-=a[n-1] else x+=a[0]; //양끝단을 비교, 맨끝이 더크면 양수값의 최댓값이, 가장 앞이 크면 음수값이 최댓값이 크다는 것을 의미, 더 큰것을 마지막으로 (즉 *2가 아니라 *1 이다)
writeln(x); //출력
end.

 

풀이 : 정렬

 

1. 여러 sort기법으로 오름차순 정렬을 합니다.

2. 배열의 가장 처음 부분부터 시작하며 음수값이라면 그 값에 * (-2)을 한 값을 따로 누적시켜주고, +m 만큼 인덱스를 이동시킵니다. 양수값이 뜬다면 종료합니다.

3. 배열의 가장 맨 끝 부분부터 시작하며 양수값이라면 그 값에 * (+2)을 한 값을 따로 누적시켜주고, -m 만큼 인덱스를 이동시킵니다. 음수값이 뜬다면 종료합니다.

4. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 즉 이동거리를 줄일려면 맨처음과 맨 끝에 있는 책중 더 0에서 먼 거리를 마지막으로 하는 것이 좋습니다. 고로 두 개의 절댓값을 비교한다음, 더 큰 값을 2,3에서 구했던 이동거리의 누적값에서 빼주면 됩니다.

 

ex)

50*2 + (-45) * (-2) + (-9) * (-2) 가 책을 두고 다시 0좌표로 돌아오는 최소한의 이동거리이나 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 라는 말이 있으므로 양끝단 중 더 값이 큰 50 (50 > 45) 을 마지막으로 가면 되며 고로

50*2 + (-45) * (-2) + (-9) * (-2) - 50 = 158 을 해주면 됩니다.

 

주의)

책의 위치는 0이 아니며 , 라는 조건을 잊어서는 안됩니다.

 

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