[알고리즘 스터디] 백준 #1461 도서관

 

문제 

도서관 영업 후에 책 정리를 할 것이다. 

재훈이의 현재 위치는 0이고, 각 책들의 위치는 절댓값이 10000이하인 정수이며, 0 위치에 있는 책은 없다.

한 번에 M개의 책을 운반할 수 있다고 할 때, 책을 모두 정리하는데 필요한 최소 걸음횟수를 구해라 .

(마지막 책을 정리한 후에는 다시 원점으로 돌아올 필요가 없다.)

 

입력

N : 책의 개수 (1<=N<=10000)

M : 한 번에 운반할 수 있는 책의 개수 (1<=M<=10000)

각 책의 위치가 N개의 숫자로 입력된다. (-10000<=x<=10000)

 

풀이

 

사용한 알고리즘은 다음과 같다. 

위치가 -인 책과 +인 책은 따로 나누어 생각하는 것이 좋다. 

(-와 +인 책을 한번에 들고 운반할 경우, 경로 사이에 어차피 원점을 지나게 되기 때문이다.)

 

가장 먼 책을 기준으로 M개를 정리할 때 드는 왕복 걸음횟수는 가장 먼 책의 위치에 영향을 받는다.

ex) 100, 10, 1 이렇게 세개의 책을 정리한다고했을 때 어차피 100위치에 다녀와야 하기 때문이다. 

 

마지막 책을 정리한 이후에는 돌아올 필요가 없다. 재훈이가 k번 왔다갔다 해야하는 경우에 

거리가 제일 먼 책을 정리할 때 돌아오지 않는것이 유리하다. 

ex) 36, 80 두권의 책을 정리하고, 한 번에 한권의 책만 운반할 수 있다고 하자.

마지막에 80을 정리하는 경우 : 36*2+80 = 152

마지막에 36을 정리하는 경우 : 80*2+36 = 196

따라서 가장 멀~리 가야하는 경우를 마지막에 정리하는 것이 유리하다는 것을 알 수 있다. 

 

예시

보라색으로 칠한 수들(각 그룹의 최댓값) 중에 가장 큰 값은 마지막에 정리하는 것으로 해서 편도로 계산하였다. 

 

코드 

 

#include <stdio.h>
#include <algorithm>
using namespace std;
bool desc(int a, int b) { return a > b; } //내림차순 정렬을 위한 함수 
int main() {
	int n, m,temp;
	int pnum = 0; int nnum = 0; //각각 거리가 양수/음수인 책의 개수를 담는 변수 
	int pbooks[10001]; int nbooks[10001];
	scanf_s("%d %d", &n, &m);
	for (int i = 0;i < n;i++) {
		scanf_s("%d", &temp);
		if (temp > 0) 
			pbooks[pnum++]=temp;
		else 
			nbooks[nnum++] = -1 * temp;
	}
	sort(pbooks, pbooks + pnum,desc); //거리가 먼 순서로 정렬 
	sort(nbooks, nbooks + nnum,desc);
	int idx = 0; //각 배열에 책들이 거리가 먼 순으로 정렬되어 있기 때문에 0번책을 가장 먼저 정리 
	int result = 0;
	int M = 0;
	while (idx < pnum) { //책을 모두 정리할 때 까지 ! 
    	//사실 이 if문은 어차피 책들이 정렬되어있기 때문에 굳이 필요 없는듯.. 
		if (pbooks[idx] > M) { //지금 정리한 책이 가장 멀리있는 책일 경우 
			result += pbooks[idx]; //가장 먼 거리는 편도! 한번만 더하기! 
			result += M; //M이 편도라서 한번만 더해져있었기 때문에 왕복거리로 계산해주기 위해 한번 더 더함 
			M = pbooks[idx]; //M값 갱신 
		}
		else
			result += (pbooks[idx] * 2); //왕복 거리 더해주기 
		idx += m; //한 번에 m권 씩 정리하니까 
	}
	idx = 0; //idx 초기화 
	while (idx < nnum) {
		if (nbooks[idx] > M) { //필요없는..부분..
			result += nbooks[idx];
			result += M;
			M = nbooks[idx];
		}
		else
			result += (nbooks[idx] * 2);
		idx += m;
	}
	printf("%d", result);
	
}

책과 원점간의 거리를 이용한 문제이기 때문에, - 거리인 경우에 양수로 바꾸어서 저장해주었다. 

(그래서 아예 양수와 음수를 다른 배열에 저장해서 따로 처리하였다.)

 

최종 거리 계산에 이용되는 숫자들을 따로 배열에 저장하기가 싫어서, while문을 돌면서 바로바로 더하되, max값을 매번 갱신해 주면서 최소거리를 계산했다. 

 

 

다른 풀이들

https://kimpika.tistory.com/55

[백준] 1461: 도서관

이 분은 벡터를 이용해서 푸셨다. + 그리디 알고리즘 

그리디 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다.

이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이다. 

 

https://zoonvivor.tistory.com/137

[BOJ] 백준 1461 - 도서관 (자바)

이 분은 우선순위 큐를 사용하셨다. 

 

사용한 변수 타입은 조금씩 다르지만 근본적인 알고리즘은 다들 비슷한 것 같다.