KOI 2019 1차 고등부 2번 / 점프 - 17613

#include <iostream>
using namespace std;
 
int arr[31];
 
int getIdx(int u) {
    int ret;
    for(ret = 0; ret<31; ++ret)
        if(arr[ret] > u) return ret-1;
}
 
int cal(int n) {
    return 1+n*(n+1)/2;
}
 
int divide(int s, int e, int p) {
    if(!s && !e) return p;
    int idx;
    int ne = e;
    int ret = 0;
    while(true) {
        idx = getIdx(ne);
        if(arr[idx] <= s) break;
 
        if(arr[idx]*2 == ne) ret = max(ret, cal(idx));
        else ret = max(ret, divide(0, ne-arr[idx], idx));
        ne = arr[idx] - 1;
    }
    ret = max(ret, divide(s-arr[idx], ne-arr[idx], idx));
    return ret + p;
}
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int T; cin >> T;
    arr[0] = 0;
    arr[1] = 1;
    for(int i = 2; i<31; ++i)
        arr[i] = 2*arr[i-1] + 1;
    int u, v;
    for(int tn = 0; tn<T; ++tn) {
        cin >> u >> v;
        cout << divide(u, v, 0) << "\n";
    }
}

 

 

 

 

 

www.acmicpc.net/problem/17613

17613번: 점프

 

 

 

 

 

점프

한번 점프를 하면 초항이 1이고 등비가 2인 공비수열처럼 점프를 계속 하게 됩니다.

따라서 특정 수 a에 도달하기 위해 최소로 점프를 하는 방법은 점프를 최대한 초기화 시키지 않고 a에 근접하게 가고, 점프를 초기화, 그리고 거기서 또 a에 가장 근접하게 점프를 계속 하고 점프를 초기화... 이런 방법을 반복해서 가는 것이 가장 적은 점프수로 a에 도달 할 수 있는 방법입니다.

 

따라서 우리는 전체 수를 [2^n-1, 2^(n+1)-2] 이란 특정 구간들로 모두 나눌 수 있고,

특정 [s, e]구간이 존재한다면, [s, e]사이의 구간 [a, b]가 특정 [2^n-1, 2^(n+1)-2] 구간에 포함된다면, 

[a, b]구간에서 최소점프로 갈수 있는 곳에 도달하기 위한 점프수를 J(n)이라 하고

[a- (2^n-1), b - (2^n-1)]구간에서 최소점프로 갈 수 있는 곳에 도달하기 위한 점프수를 J'(n)이라고 한다면

J(n) = J'(n) + n 이라는 점화실을 얻을 수 있습니다.

 

따라서 구간 [s, e]를 위의 점화식 조건을 사용 할 수 있게 [s, b(0)], [a(1), b(1)], .... , [a(n), e] 로 나누고 점화식을 사용 한다면 각각의 나누어진 구간에서 최소점프로 갈수 있는 곳중 최대의 점프 횟수를 구할 수 있습니다.

 

이때 [2^n-1, 2^(n+1)-2]과 같은 자주사용되는 특정 구간에 대해 최소점프로 갈수 있는 곳중 최대 점프의 수를 DP로 저장해준다면, 우리는 훨씬 더 빠른 시간안에 문제를 해결 할 수 있습니다.

 

아니면, [2^n-1, 2^(n+1)-2]의 조건의 최대값은 [0, 2^(n+1)-2]의 조건의 최대값과 같고, 

[2^n-1, 2^(n+1)-2]의 최대값은 [0, 2^n-2]의 최대값 + n을 한것과 같습니다 따라서 

특정 구간 [2^n-1, 2^(n+1)-2]의 최대값은 1+n*(n+1)/2 라는 식을 얻을 수 있습니다.