Boj 1422) 숫자의 신

문제

백준 1422

설명

a+b < b+a 이 Strick Weak Ordering 을 만족한다고 가정하자. 그러면 이 비교식을 이용해 정렬을 한 결과를 순서대로 합치는 것이 최적이라는 것은 쉽게 증명할 수 있다.　

임의의 수열에서 a+b < b+a 인 두 항이 연속되어 있다면(... a, b ...) 그 순서를 바꾼 수열(... b, a ...) 이 더 크다. 이 과정은 버블소트의 과정과 같으므로 유한한 단계 내에 임의의 수열보다 같거나 더 최적인 정렬된 수열을 만들 수 있다. 이는 최적인 수열에도 동일하게 적용 가능하므로 위 비교식으로 정렬한 수열이 최적이다.

하지만 a+b < b+a 이 Strick Weak Ordering 을 만족하는지는 증명하기가 까다롭다.

Transitivity of Equivalence

a+b == b+a 라는건 gcd(len(a), len(b)) 의 어떤 약수를 길이로 하는 청크로 a, b 가 쪼개질 수 있다는 의미이다. 여기서 추가로 b+c == c+b 의 조건이 주어지면 gcd(len(a), len(b), len(c)) 의 어떤 약수를 길이로 하는 청크로 a, b, c 가 쪼개진다는 의미이다. 그러므로 a+c = c+a 가 성립하게 된다.

Transitivity

Transitivity 를 만족하기 위해선 a+b < b+a 이고 b+c < c+b 이면 a+c < c+a 임을 보여야한다. 혼자서 이를 증명해보려다 포기하고 질문을 했더니 답지를 받았다. 그것을 여기다 기록한다.

문자열을 비교할 때 앞부분의 공통 문자열은 영향을 끼치지 않는다. 그런데 이를 살펴보면 신기한 성질이 하나가 있다. 이를 보이기 위해 어떤 문자열 \(a\) 에 대해서 \(R(a) = a[1] + ... a[\mathrm{len}(n)] + a[0]\) 을 정의한다. 맨앞 문자를 뒤로 빼는 함수이다. 그러면 임의의 문자열 \(a\), \(b\) 에 대해서 다음이 성립한다.

Lemma 1. \(\quad (a[0] = b[0]) \wedge (a+b < b+a) \iff R(a)+R(b) < R(b)+R(a)\)

증명은 간단하다. 공통된 문자를 z 로 두고 a = z + a', b = z + b' 로 두자.

a+b < b+a <=> z + a' + z + b' < z + b' + z + a' 이다. 여기서 앞의 z 를 뒤로 빼도 같은 문자이므로 두 문자열의 대소관계는 변하지 않는다. 그러므로 R(a)+R(b) = a' + z + b' + z < b' + z + a' + z = R(b)+R(a) 가 성립한다.

Proposition. \(\quad (a+b < b+a) \wedge (b+c < c+a) \implies a+c < c+a\)

전제 상 \(a[0] \leq b[0] \leq c[0]\) 이다. 이는 다음과 같은 세 경우로 나뉜다.

• \(a[0] < b[0]\) 라고 하자. \(a[0] < b[0] \leq c[0]\) 이므로 \(a<c\) 이다.
• \(b[0] < c[0]\) 라고 하자. \(a[0] \leq b[0] < c[0]\) 이므로 \(a<c\) 이다.
• 그러면 \(a[0] = b[0] = c[0]\) 인 경우가 남는다. Lemma 1 에 의해 주어진 조건은 \(R(a) + R(b) < R(b) + R(a)\) 이고 \(R(b) + R(c) < R(c) + R(b)\) 임과 동치가 된다. 그러므로 \(R(a), R(b), R(c)\) 에 대해 위의 작업을 똑같이 수행한 결과를 사용할 수 있다. 각 문자열은 다르므로 위의 두가지 케이스 중 하나에 반드시 걸리게 되고 이는 오직 \(a<c\) 뿐이다.
• 모든 경우에서 \(a<c\) 이므로 증명완료.

비슷한 문제들

큰 수 만들기

• 이 문제의 기본형 문제로 0 처리만 안까먹으면 됨.

도도의 수학놀이

• 문자열 전체를 뒤집는건, 수열의 원소 각각을 뒤집고 수열의 순서를 뒤집는 것과 같음을 이용
• 문자 하나 추가는 이 문제의 옵션과 다를게 없다

Secret Sharing

• 0 으로 시작하는 문자를 제외한 맨 앞 문자를 이 문제에서 사용한 정렬을 이용해서 구하는 문제

시간 복잡도

O(\(10\mathrm{N}\log{\mathrm{N}}\))

• 자리수의 크기만큼 문자열 비교에 시간이 걸리고 10자리 수가 최대라서 10을 곱함

코드

string arr[51];
bool compare1(const string& a, const string& b) { return a + b > b + a; }

bool compare2(string& a, string& b)
{
	// 제일 큰 자리수거나, 같은 자리수면 더 큰 수를 선택
	if(a.size() != b.size()) 
		return a.size() > b.size();
	return a > b;
}

int main()
{
	int k, n;
	cin >> k >> n;
	for (int i = 0; i < k; i++) cin >> arr[i];
	sort(arr, arr + k, compare2); // 대충 정렬로 최대수 찾기
	string end = arr[0];
	sort(arr, arr + k, compare1);

	int nInsert = n - k;
	string ans;
	for (int i = 0; i < k; i++) {
		if (arr[i] == end)
			while (nInsert-- > 0) ans += end;
		ans += arr[i];
	}

	cout << ans;
}