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

문제링크: https://www.acmicpc.net/problem/1461

1461번: 도서관

 

접근방식

 

1.  정렬을 하고, 문제를 해결해야함을 인지

2.  정렬을 하고 최선의 선택을 하며 결과를 도출하는 그리디임을 인지 

3.  양수, 음수별로 진행 -> m개씩 전달하는 값을 도출 -> 가장 먼 값은 왕복이 아님

 

 

문제풀이 

 

1. 2. 예시에서는 -37 2 -6 -39 -29 11 -28 -> -39 -37 -29 -28 -6 2 11

3.  {-39} {-37 -29} {-28 -6} {2 11} 이렇게 4번 진행하되 -39를 마지막에 도달하면 131이 나옴

4. 즉,  음수 양수 따로 진행하며,  m개씩 선택하고 왕복값을 저장해준다. 그리고 가장 극단 값에 있는 값을 빼줌 (왕복x)

 

 

 

그리디 알고리즘 문제였습니다.

아래는 정답코드입니다.

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int n, m;
int arr[10001] = { 0, };
int pindex = 0;
int result = 0;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (arr[i] < 0)
			pindex++;
	}

	sort(arr, arr + n);
	
	for (int i = n - 1; i >= pindex; i -= m) {
			result += (arr[i]*2);
	}

	for (int i = 0; i < pindex; i += m) {
			result += abs(arr[i] * 2);
	}

	result -= max(abs(arr[0]), abs(arr[n - 1]));

	cout << result << endl;
	return 0;
}