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

 

문제를 곧이 곧대로 풀면 시간초과가 나옵니다. 테스트 케이스도 여러개고, N이 10억까지기 때문에 한번씩 해보는건 불가능합니다.

N의 범위가 크기 때문에 dp도 안됩니다.

이럴 때는 분명히 상수시간에 나오는 해법이 있습니다.

 

일단 \(C=(\text{n보다 한자릿수 큰 } 10^a \text{형태의 수})\)라고 할 때, \(F(n)=C - n - 1=-n+(C-1)\) 입니다.

예를 들어 \(F(124) = -124 + 1000 - 1 = 875\)입니다.

 

따라서 사랑스러움에 대해 식으로 나타내보면 \(y = n \times F(n) = n \times (-n + (C-1))\).

n에 대한 이차방정식으로 생각해보면 \(n=0\) 또는 \(n=C-1\)일 때 \(y=0\)이고, \(n^2\)의 부호가 음수이므로 위로 볼록한 형태입니다. 이건 고등학교때 배운 내용이죠

이때 최대값은 \(n=(C-1)/2\)일 때인데, C-1이 항상 홀수이므로(C는 짝수) \(\lfloor(C-1)/2\rfloor\), \(\lceil(C-1)/2\rceil\) 둘 다 같은 값을 가지면서 정수 domain의 y에 대해 최대값을 갖게 됩니다

 

따라서 입력 n에 대해 \(n \times min(n, \lfloor (C-1)/2 \rfloor)\)가 [1, N] 범위 수의 사랑스러움 중 최대값이 됩니다

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

inline ll f(ll n) {
	ll exp = 1;
	while (n >= exp) {
		exp *= 10;
	}
	return exp - n - 1;
}

inline ll biggest(ll n) {
	ll exp = 1;
	while (n >= exp) {
		exp *= 10;
	}
	return min((exp/2)-1, n);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int t;
	cin >> t;

	while (t--) {
		ll n;
		cin >> n;

		ll target = biggest(n);
		cout << target * f(target) << '\n';
	}
	
	return 0;
}

10^a 계산할 때 long long을 써야 합니다. 입력으로 10억이 들어오면 100억이 되기 때문에 32비트 정수형은 오버플로우가 발생합니다. 계산할 때도 마찬가지입니다.

반응형