[백준 2548] 대표 자연수

난이도

실버 III

📜문제

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

🌞풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> v;
	int answer = 0;
	int minimum = 999999999;

	int N = 0;
	cin >> N;

	int value;
	for (int i = 0; i < N; i++)
	{
		cin >> value;
		v.push_back(value);
	}
	sort(v.begin(), v.end()); // 오름차순 정렬

	for (int i = 0; i < N; i++)
	{
		int cnt = 0;
		int result = 0;
		for (int j = 0; j < N; j++)
		{
			if (v[i] > v[j]) // 차를 구한다.
			{
				result += v[i] - v[j];
				cnt++; // 기준값보다 작다면 cnt + 1
			}
			else result += v[j] - v[i];
		}
		if (result < minimum)
		{
			minimum = result;
			answer = v[i];
		}
		if (cnt > N / 2) break; // cnt가 절반보다 많아 질 경우
	}
	cout << answer << "\n";
	return 0;
}

• 오름차순 정렬을 하고 제일 작은 수 부터 기준으로 값을 구해 나간다.

ex) 4 3 2 2 9 10 인 경우
오름차순 정렬 : 2 2 3 4 9 10

기준값               합     기준값보다 작은 수
  2 : 0 0 1 2 7 8   18
  3 : 1 1 0 1 6 7   16           2 2
  4 : 2 2 1 0 5 6   16           2 2 3
  9 : 7 7 6 5 0 1   26           2 2 3 4
 10 : 8 8 7 6 1 0   30           2 2 3 4 9

• 오름차순으로 정렬을 했기 때문에 한번 기준값보다 작아지면 계속 기준값보다 작다.
  • 그렇기 때문에 cnt가 절반을 넘어가는 경우 부터는 어떠한 수 배열이 나와도 값이 작아질수가 없다.

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기