[BOJ 17613 // C++] 점프

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17613번 문제인 점프이다.
문제는 아래 링크를 확인하자.

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

17613번: 점프

 

양의 정수 N이 주어졌을 때, 0에서 출발하여 더 이상 이동할 수 없을 때(즉, 이전 점프거리의 두배를 점프하면 N을 넘어가게 되기 전)까지 점프 거리를 늘려나가다 초기화를 반복하는 것으로 J(N)회의 이동을 할 수 있음을 직관적으로 알 수 있다. 이 증명은 독자에게 맡긴다.

 

위의 성질을 이용하면 \([2^k-1,2^{k+1}-1)\)에 속한 정수 N에 대하여 J(N)의 값은 \(k+J(N-2^k+1)\)와 같이 계산할 수 있음을 알 수 있다.

 

구간 [L,R]이 입력으로 주어질 때, 해당 구간을 이 범위 내의 가장 큰 \(2^k-1\)의 값 X를 기준으로 해당 수 이상인 수와 그렇지 않은 수들에 대해 경우를 나누어가며 문제를 해결하자. 이 과정에서 구간이 둘로 쪼개질 경우 더 큰 수가 포함되어있던 구간은 k회의 이동으로 \(2^k-1\)의 거리를 이동하게 됨을 이용해 범위의 수를 줄여나가게 된다. 이후의 이쪽 구간의 분할과정은 \([0,2^k-1)\)의 고정된 형태를 하나씩 포함하고 있으므로 이러한 구간의 답을 메모이제이션해두면 시간복잡도를 줄여 문제를 시간 내에 충분히 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <map>
using namespace std;
typedef long long ll;

int T;

map<ll, int> dp;

int func(ll L, ll R) {
	if (dp.count((L << 32) + R)) return dp[(L << 32) + R];
	
	int ret;
	ll exp2 = 1; int k = 0;
	while ((exp2 << 1) - 1 <= R) exp2 <<= 1, k++;
	exp2--;

	if (L >= exp2) ret = k + func(L - exp2, R - exp2);
	else ret = max(func(L, exp2 - 1), k + func(0, R - exp2));

	dp.insert({ (L << 32) + R,ret });
	return ret;
}

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

	dp.insert({ 0,0 });

	cin >> T;
	while (T--) {
		ll L, R; cin >> L >> R;
		cout << func(L, R) << '\n';
	}
}