[백준] 1461 도서관 (C++)

백준 1461 도서관

1. 문제

문제 링크

2. 접근법

[ 문제 접근 ]

 

그리디 알고리즘을 사용하여 푸는 문제였다. 

1. 맵을 오름차순으로 정렬한다.

2. 양수와 음수를 따로 계산해주기 위해 입력받을 때, 음수의 개수만큼 인덱스를 하나씩 증가시킨다. 

3. 한 번에 들 수 있는 최대 개수 M만큼 for문을 돌리면서 왕복해야 하기 때문에 거리*2만큼 ans에 담아준다.

4. 최단거리를 구해야 하고, 마지막에는 출발지점까지 올 필요가 없으므로 양 끝점의 값 중 더 큰 값을 ans에서 빼주면 된다.

3. 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int map[10001];
int N, M;
int idx, ans;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		cin >> map[i];
		if (map[i] < 0)
			idx++;
	}
	sort(map, map + N);
	for (int i = N - 1; i >= idx; i -= M)
	{
		ans += (map[i] * 2);
	}
	for (int i = 0; i < idx; i += M)
	{
		ans += abs(map[i] * 2);
	}

	ans -= max(abs(map[0]), abs(map[N - 1]));
	cout << ans << "\n";

	return 0;
}

4. 결과