[C/C++ 백준 1461번] 도서관 (Silver 1)

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

1461번: 도서관

굉장히 까다로웠던 문제였다.

마지막에 책을 가져다놓는것은 가장 먼거리에 있는 책이고, M개씩 책을 들고 다닐수 있으므로 M개씩 끊어서 최대거리를 2배 곱해 더해주고, 가장 먼거리는 한번만 더해 값을 구해주면 된다.

 

좌표축을 기준으로 0 오른쪽에 있는 책들은 plus배열에, 0 왼쪽에 있는 책들은 minus배열에 저장해준다. (이후 내림차순 정렬)

일단 마지막에 책을 갖다 놓는 경우는 생각을 안하고 모두 2배를 곱해 더해준 뒤, 나중에 가장 큰 거리를 빼주자.

가장 효율적으로 책을 운반하는 것은 먼 거리를 갔다 올때 먼 거리에 있는 책들을 한꺼번에 해결하는 것이므로, 배열에서 0, M, 2M..번째 책들 운반을 기준으로 거리를 더해주자. 남은 책들도 그냥 운반한다고 하고 더해준뒤, 가장 큰 거리를 빼면 답을 구할 수 있다.

 

 

 

#include <cstdio>
#include <algorithm>
using namespace std;
bool comp(int a, int b){
	return a>b;
}
int main(void){
	int plus[10001], N, M, num, pluscnt=0, minuscnt=0;
	int minus[10001], cnt=0, ans=0;
	scanf("%d %d",&N,&M);//입력받기
	for(int i=0; i<N; i++){
		scanf("%d", &num);
		if(num>0)
			plus[pluscnt++]=num;//양수면 +, 음수면 -에
		else
			minus[minuscnt++]=num*(-1);
	}
	sort(plus, plus+pluscnt, comp);
	sort(minus, minus+minuscnt, comp);
	if(pluscnt!=0){//plus 배열 처리해주기
		while(1){
			if(cnt%M==0)
				ans += plus[cnt]*2;//M개씩 들고 다니니까 앞에서부터 M개씩 빼줌
			if(cnt==pluscnt-1)// 책 다 가져다 놓음
				break;
			cnt++;
		}
		cnt = 0;	
	}
	if(minuscnt!=0){//minus 배열 처리해주기
		while(1){
			if(cnt%M==0)
				ans += minus[cnt]*2;
			if(cnt==minuscnt-1)
				break;
			cnt++;
		}	
	}
	ans -= max(plus[0], minus[0]);//최대 거리 하나 빼주기
	printf("%d",ans);
}