[백준] 1060 좋은 수

문제

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

 

풀이

문제가 상당히 수학적이라 바로 이해하기 힘들다.

풀이를 해보기 전에 이 글에서 사용할 용어 몇 가지를 약속하고 가자.

• 숫자 집합 S = {s(0), s(1), ... , s(L-1)} 와 같은 형태이다.
• S 구간이란, S의 원소가 아닌 연속된 정수들의 구간이다.
  • 예를 들면 S = {s(0), s(1), s(2)} 일 때 S구간은 (1, s(0)), (s(0), s(1)), (s(1), s(2)), (s(2), 무한대) 가 있다.
  • S구간의 오른쪽에 오는 원소가 s(n)이면 해당 S구간은 S(n)이라고도 한다.
• x가 포함된 좋은 구간의 갯수는 i다.

 

어떤 수가 더 좋은 수인지 판단하기 위해서는 어떤 수가 몇 개의 좋은 구간을 가지고 있는지 알아야 한다.

어떤 수 x의 좋은 구간의 갯수 i를 구하기 위해서는 x가 어떤 S구간에 포함된 수인지 알아야한다.

x가 S(n)에 포함되어 있고, x가 포함된 좋은 구간을 [a, b]라고 했을 때, 아래와 같은 조건이 성립된다.

s(n-1) < a <= x <= b < s(n)

a와 b의 가능한 숫자의 범위에 따라 가능한 숫자의 갯수를 구할 수 있다.

a의 가짓수 =  (x-s(n-1) +1) 

b의 가짓수 =  (s(n)-x +1) 

그리고 좋은 구간[a, b]의 가능한 가짓수, 즉 좋은 구간의 갯수 i는 a의 가짓수 x b의 가짓수 -1와 같다.

마지막에 1을 빼준 이유는 [x, x]는 불가능하기 때문이다.

따라서 S(n)에 포함된 x의 i의 공식은 아래와 같다.

i = (x-s(n-1) +1) * (s(n)-x +1) -1 

그리고 이것을 그래프로 그리면 대략 아래와 같다.

특징적으로 봐야할 부분은 다음과 같다.

• x가 포함된 S구간의 길이가 짧을 수록 i가 작다.
• x가 자신이 포함된 S구간의 중앙에서 멀수록 i가 작다. 
• x가 s(n)과 같을 경우 i는 0이 된다.
• 마지막 S구간에 포함된 x들의 i는 무한대다.

즉, 어떤 수가 좋은 수인지는 해당 수가 얼마나 짧은 S 구간에 포함되어 있느냐, 그리고 x가 얼마나 S구간의 가생이에 존재하느냐 가 중요하다.

 

이 사실을 깨달았다면 본격적인 풀이가 가능하다.

1. map에 모든 s로부터의 거리가 n 이하인 수 x와 x에 대한 i를 pair로 만들어 넣는다. 
2. 그리고 x를 priority_queue에 삽입한다.
   1. 이 때 priority_queue의 조건자가 중요하다.
   2. 조건자는 i가 작을수록, i가 같다면 x가 작을수록 높은 우선순위를 갖도록 한다.
3. n개의 숫자를 priority_queue에서 pop하고 출력한다.

이 떄 x를 s로부터의 거리가 n 이하인 수로 할 수 있었던 것은,  n과 L이 각각 100이하, 50이하이기 때문에 가능한 풀이다. 이 숫자가 커지면 다른 방법을 찾아보아야 할 것이다.

 

코드

// CodeTest.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include<cstring>
#include <queue>

using namespace std;

int L;
vector<int> S;
int n;
map<int, long long> m;
long long GetSectorCount(int num, int part)
{
	long long left = 1;
	long long right = 0;
	if (part < L && S[part] == num)
		return 0;
	if (part == 0)
		right = S[0]-1;
	else if(part  == L)
		return -1;
	else
	{
		left = S[part-1] + 1;
		right = S[part] -1;
	}
		
	return (num-left +1) * (right - num +1) -1;
}
struct Cmp
{
	bool operator()(int a, int b)
	{
		long long aCount = m.find(a)->second;
		long long bCount = m.find(b)->second;

		if (aCount == bCount)
			return a > b;
		if (aCount == -1)
			return true;
		if (bCount == -1)
			return false;
		return aCount > bCount;
	}
};

int main()
{
	cin >> L;
	S.resize(L);
	for (size_t i = 0; i < L; i++)
	{
		int input; cin >> input;
		S[i] = input;	
	}
	cin >> n;
	sort(S.begin(), S.end());
	priority_queue<int, vector<int>, Cmp> q;
	for (size_t i = 0; i < L; i++)
	{
		int left;
		int right;

		if (i == 0)
		{
			left = 1;
			right = S[0];
		}
		else
		{
			left = S[i-1];
			right = S[i];
		}
		int count=0;
		for (size_t j = left; j <= right && count < n; j++,count++)
		{
			if (m.find(j) == m.end())
			{
				m.insert({ j,GetSectorCount(j,i) });
				q.push(j);
			}

		}
		count = 0;
		for (int j = right ; j >= left && count < n; j--, count++)
		{
			if (m.find(j) == m.end())
			{
				m.insert({ j ,GetSectorCount(j,i) });
				q.push(j);
			}

		}
	}
	for (size_t i = 1; i < n+1; i++)
	{
		int val = S[L - 1] + i;
		m.insert({val,GetSectorCount(val,L)});
		q.push(val);
	}
	for (size_t i = 0; i < n; i++)
	{
		cout << q.top()<<' ';
		q.pop();
	}
}