BOJ 1056 - 수

* BOJ 1056 - 수

[분류 - 정수론, 가지치기, 다이나믹 프로그래밍, 최단경로 알고리즘]

  수의 범위만 봐도 10^18이기 때문에 메모리나 시간 측면에서 단순 다이나믹이나 BFS로 구현할 수 없는 문제입니다. 이 사실만 봤을 때 가지치기가 필수임을 알 수 있는데, 1번과 2번 연산으로는 절대로 시간이나 메모리를 줄일 수 없습니다. 따라서 3번 연산을 가지고 놀아야해요.

  반대로 N에서 1로 만든다고 생각하고 진행해봅시다.

[해설]

  전제 1) 임의의 수 N에 대해 어떤 자연수 x제곱에 가장 가까운 지점은 최대 두 개의 지점이 있다. 하나를 a^x라고 하면 또 다른 하나는 (a+1)^x로 둘 수 있다. 즉, 두 지점의 밑은 정확히 1 차이가 난다.

  증명 1) 가장 가까운 두 지점이 a^x, (a+y)^x라고 둬보자(단, y > 1인 정수). 그러면 수식 관계에서 모두 양의 정수이기 때문에 a^x < (a+1)^x < (a+y)^x임을 알 수 있다. 여기서 a^x가 N에 가까운 정수 중 가장 작은 정수로 가정했기 때문에 N은 a^x <= N, N <= (a+1)^x이므로 (a+y)^x가 N에서 가장 가까운 지점이라고 볼 수 없다. 따라서 가장 가까운 두 지점의 밑의 차이는 정확히 1이다.

  전제 2) 임의의 수 N에 대해 3번 연산을 사용하기 위한 k와 거리가 2 * 10^9이하이다. (|N-k| < 2 * 10^9)

  증명 2) 어떤 자연수 x제곱이 N의 주변에 있다고 치자. 전제1)에 의해 하나는 a^x, 또 다른 하나를 (a+1)^x로 둘 수 있다. 이 두 지점은 N으로부터 가장 가까운 지점임을 인지하며 두 지점의 거리 (a+1)^x-a^x를 최대로 하는 a, x값을 구하면 a=999999999, x=2임을 알 수 있다. 따라서 |N-k| <= (1000000000 - 999999999) * (1000000000+999999999) < 2 * 10^9 이다.

  전제 3) a(a > 1)에 대해 a^b=k라고 할 때, b 값의 범위는 [2, 62]이다.

  증명 3) 임의의 수 N이 10^18까지 올라가므로 a 자연수 b제곱인 k값은 커봤자 10^18에 근접해야 한다. 이 값은 2^62=4611686018427387904 > 10^18이므로 b의 최대값은 62이다.

  전제 4) [그리디] 임의의 N에서 1로 만드는 연산의 최소값으로 표기하고 이를 아래처럼 표기할 수 있다. 단, 와 는 자연수 x제곱 중 N과 가장 가까운 두 수.

  증명 4) 자연수 x제곱에 대해 (a+1)^x보다 멀리 있는 (a+y)^x (즉, y > 1)이 최적이라고 가정해보자. 그러면 이 때의 값은  + |N-(a+y)^x| + 1가 된다. 이 값이 더 작기 위해선  + |N-(a+1)^x| + 1 > + |N-(a+y)^x| + 1 수식을 만족해야 한다. 과 의 차이와 |N-(a+1)^x|과 |N-(a+y)^x|의 차이를 비교하자면 전자는 만큼 줄어들었기 때문에 후자의 차이가 압도적으로 크다(x > 1). 따라서 위 수식을 만족하는 y값은 존재하지 않기 때문에 위 전제 4)는 참이다.

[구현]

  요약하자면 현재 값 N에 대해 x=[2, 62] 그리고 임의의 자연수 a에 대해 자연수 x제곱 a^x 중 가장 가깝고 N보단 작은 a값을 찾고 a^x와 (a+1)^x에 대해 와 를 재귀적으로 찾아가도록 구현하면 됩니다. 범위를 보면 x가 최소 2이므로 수의 범위가 최소한 으로 줄어들 게 됩니다. 매번 3번 연산을 할 때마다 탐색 범위가 큰 폭으로 줄기 때문에 시간이 모자랄 수 없습니다.

  또 는 한 번만 방문하고 그 값을 다시 저장해두는 다이나믹 프로그래밍 방식을 쓰면 위 구조를 깔끔하게 쓸 수 있습니다.

  마지막으로 매 재귀마다 x를 2부터 62까지 증가하는 반복문으로 두고, 전제 4)에 만족하는 a를 이분탐색으로 찾아서 값을 계산하시면 됩니다(저는 a+1를 찾는 방식을 채택했습니다).

※ 오버플로우에 주의

#include<cstdio>
#include<unordered_map>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
using ll = long long;
const ll LIMIT = (1ULL << 63) - 1, RANGE = 2e9;
const double LOG_L = log(LIMIT);
ll limit[63] = {};

// a^n
ll _pow(ll a, int n) {
	if (n <= 1) return n % 2 ? a : 1;
	ll h = _pow(a, n >> 1);
	return h * h * (n % 2 ? a : 1);
}

// n보다 크거나 같은 a^k에 대해 a를 찾는 함수. 단, maxi보다 커질 순 없음. maxi는 g함수에 의해 계산됩니다.
ll f(ll& n, int k, ll& maxi) {
	ll l = 1, r = maxi;
	ll mid;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (_pow(mid, k) < n) l = mid + 1;
		else r = mid - 1;
	}
	return l;
}

// a^k 꼴에서 오버플로우를 방지하기 위해 a의 최대값을 찾는 이분탐색
ll g(int k) {
	ll l = 2, r = 1LL << 40, mid;
	mid = (l + r) >> 1;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (k * log(mid) + 1e-9 <= LOG_L) l = mid + 1;
		else r = mid - 1;
	}
	return r;
}
unordered_map<ll, ll> dp; // 이미 방문했던 지점을 두 번 이상 방문하지 않기 위함. 다이나믹 프로그래밍
ll gv(ll n) {
	if (n == 1) return 0;

	ll& ret = dp[n];
	if (ret) return ret;
	ret = n - 1; // 1부터 1씩 증가해서 접근하는 경우의 답(1번 연산)
	ll l, r;

	// 승수 고정
	// 왼쪽(변수 l), 오른쪽(변수 r)에 대해 l^i <= n <= r^i을 만족하는 값을 찾습니다.
	for (int i = 61; i > 1; i--) {
		r = f(n, i, limit[i]);
		l = r - 1;
		if (1 < l && RANGE > abs(n - _pow(l, i))) ret = min(ret, gv(l) + 1 + abs(n - _pow(l, i)));
		if (1 < r && RANGE > abs(n - _pow(r, i))) ret = min(ret, gv(r) + 1 + abs(n - _pow(r, i)));
	}
	return ret;
}
int main() {
	ll N, i;
	for (i = 2; i < 62; i++)
		limit[i] = g(i);
	scanf("%lld", &N);
	printf("%lld", gv(N));
	return 0;
}