백준17613 점프

작성일 | In

문제 출처

  • 2019 KOI 1차 고등부 2번

사용 알고리즘

  • Greedy
  • Subtask 4: Segment Tree
  • Subtask 5: DP

시간복잡도

  • Subtask 4: O(NlgN + TlgN)
  • Subtask 5: O(TlgN)
    • N = x, y의 최댓값

풀이

J(N)을 구하는 방법

J(N)을 O(lgN)에 구하는 방법을 먼저 알아봅시다.

2k-1 ≤ N을 만족하는 가장 큰 자연수 k에 대해 J(N) = k + J(N - 2k + 1) 이 성립합니다.
2k-1만큼 이동을 하기 위해서는 k번의 점프가 필요하기 때문에 k + J(N - 2k + 1) 이 됩니다.

Subtask 4

쿼리의 범위가 [1, 4000000]입니다.
J(1) ~ J(4000000)을 모두 구하는 전처리를 한 다음에 Segment Tree를 이용해 RMQ를 해주면 O(NlgN + TlgN)만에 풀 수 있습니다.
실제 대회에서는 1번 문제 100점 받고 2번 문제는 Subtask 4까지 긁어서 2교시 200점 만점에 155점을 받았습니다.

Subtask 5

O(NlgN) 전처리 없이 각 쿼리를 O(lgN)만에 처리를 해야 합니다.
J(N)는 2k-1 ≤ N을 만족하는 최대 자연수 k를 찾아서 계산을 하면 된다는 것을 알고 있습니다.

반대로 생각해서, k를 고정시켜봅시다.
2i-1 ≤ x를 만족하는 가장 큰 자연수 i가 k인 x는 [2k-1, 2k+1-2]입니다.
k=1인 구간, k=2인 구간 … 으로 구간을 나누게 되면, 모든 쿼리는 최대 O(lgN)개의 구간으로 나눌 수 있습니다.
log2(109)는 40보다 작으므로 k가 1인 경우부터 40인 경우까지 모두 봐주면서 dp를 돌려주면 됩니다. 단, dp table에서 실제로 사용하는 구간은 희소하므로 map을 이용해 메모이제이션을 하면 됩니다.

자세한 구현은 아래를 참고하시면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

map<p, int> dp;

int f(ll l, ll r){
	if(!l && !r) return 0;
	if(dp.find({l, r}) != dp.end()) return dp[{l, r}];

	int ret=  0;
	for(int i=1; i<=40; i++){ //[l, r]을 최대 O(lgN)개의 구간으로 나눔
		ll s = (1ll << i) - 1; //2^i - 1
		ll e = (1ll << (i+1)) - 2; //2^(i+1) - 2
		s = max(l, s), e = min(r, e); //범위 제한

		ll ss = s - (1ll << i) + 1; //2^i - 1만큼 점프를 하고 남은 길이
		ll ee = e - (1ll << i) + 1;

		if(s <= e) ret = max(ret, f(ss, ee) + i);
	}

	return dp[{l, r}] = ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--){
		ll x, y; cin >> x >> y;
		cout << f(x, y) << "\n";
	}
}