[BOJ] 2551 : 두 대표 자연수 - travelbeeee

문제 : https://www.acmicpc.net/problem/2551

---

[ 알고리즘풀이 ]

N 이 5,000,000 이고 들어오는 숫자의 범위가 1 ~ 10000 이므로 모든 숫자 범위(1 ~ 10,000)에 대해5,000,000 개의 N을 전체 순회하며 값을 구하면 10,000 * 5,000,000 으로 시간 초과를 받게 된다.

시간 초과 문제를 해결하려면 N은 5백만으로 크지만 숫자 범위가 1부터 10,000으로 작다는 조건에 집중해야한다.

 

-1) 1 ~ 10,000까지 들어오는 Input 을 count 해주는 list 를 하나 선언해 Input을 받으면서 count 해준다. O(5,000,000) 만에 각각 숫자가 몇 개 있는지 count 를 할 수 있다.

 

-2) 어차피 대표 자연수는 1 ~ 10,000 을 벗어나지 않으므로 1 ~ 10,000 까지 모든 수들을 대표 자연수 후보로 보고 list를 순회하며 최소값을 갱신한다.

 

list 의 크기가 10,000 이고 대표 자연수 후보도 10,000 이므로 O(10^8) 만에 대표 자연수를 구할 수 있고, 대표자연수를 구하는 2가지 방법에 대해 각각 수행하므로 O(2 * 10 ^ 8) 의 복잡도로 2초 안에 문제를 해결할 수 있다.

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

int list[10001] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, input;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> input;
		list[input]++;
	}
	int ans1 = 1, ans2 = 1;
	long long minSum1 = 999999999999999, minSum2 = 999999999999999, sum1, sum2;
	for (int i = 1; i <= 10000; i++) {
		sum1 = 0;
		for (int j = 1; j <= 10000; j++) {
			sum1 += 1LL * list[j] * abs(i - j);
		}
		if (sum1 < minSum1){
			minSum1 = sum1;
			ans1 = i;
		}
	}
	for (int i = 1; i <= 10000; i++) {
		sum2 = 0;
		for (int j = 1; j <= 10000; j++) {
			sum2 += 1LL * list[j] * (abs(i - j) * abs(i - j));
		}
		if (sum2 < minSum2) {
			minSum2 = sum2;
			ans2 = i;
		}
	}
	cout << ans1 << ' ' << ans2;
}

---