UVa Online Judge 100. (The 3n+1 problem)

요즘 다시 알고리즘을 시작한지 2주정도 지난 것 같다.

오늘은 알고리즘 트레이닝 북(Programming Challenges)을 처음 펼쳐봤는데,

(이 책을 산지는 100만년이 지난 것 같지만..)

첫 부분부터 가볍게 생각하고 문제를 봤는데,

세그먼트 트리를 사용해서 풀 수 있는 문제가 나온 것 같아서 좀 당황했었다.

보통 책 초반부는 간단한 것들을 시킬텐데....?

▶ 일단 결론부터 말하자면 책에 오타가 있었다.

실제 문제는 N제한이 10,000이었는데,

책에서는 N제한이 1,000,000이어서 ㄷㄷ

< 문제 경로: https://uva.onlinejudge.org/external/1/100.pdf >

문제는 두 정수 a,b가 주어지고, (단, 0 < a,b < 10,000)

min(a,b) ≤ x ≤ max(a,b) 인 정수 x의 f(x)값이 최대인 것을 구하는 것이다.

f(x)는 x가 짝수 일 때 2로 나누고, 홀수 일 때 3으로 곱한 후 1을 더하는데,

이렇게 해서 1에 도달할때까지 몇 번이나 연산하는지를 구하는 함수이다.

예를 들어 f(1) = 1이고, f(3) = 8 (3→10→5→16→8→4→2→1) 이다.

사실 이 문제의 테스트 케이스가 몇개 나오는지도 안 알려주는데,

AC받은 코드가 걸린 시간으로 봐서는 대충 1000개쯤 들어오는 것 같다.

문제대로 N제한이 1만일때는 그냥 무식하게 구하면 된다.

하지만 0 < a,b < 1,000,000 이라 가정한다면?

테스트 케이스가 1000개라면,

f(x)를 구하는데 걸리는 시간이 평균적으로 10이라 가정할 때

시간복잡도는 O(1000억)쯤 된다.

그래서 f(x) 구하는 것 자체를 dp형태로 바꾸고

max값 구하는 것 자체를 세그먼트 트리를 이용하여 해결할 수 있다.

일단 1부터 100만까지의 f(x)를 모두 구한 다음

이것을 max값 구하는 세그먼트 트리에 모두 업데이트하고

두 정수 a,b를 입력받으면 query를 통해 max값을 리턴하면 된다.

코드는 다음과 같다.

#include <cstdio>
#include <map>
using namespace std;
typedef unsigned int uint;
#define r2 (r<<1)
#define mm ((s+e)>>1)
map<uint,int> dp;
 
//interval: [s,e)
const int lim = 1<<23;
int seg[1<<21];
int d[lim];
const int ss=0,ee=1<<20;
 
int max(int x,int y){ return x>y?x:y; }
int update(int r,int s,int e,int at,int by) {
    if(e<=s) return 0;
    else if(at<s||e<=at) return seg[r];
    else if(s==at && s+1==e) return seg[r]=by;
    else return seg[r]=max(update(r2,s,mm,at,by),update(r2+1,mm,e,at,by));
}
 
//interval: [s,e) [i,j)
int query(int r,int s,int e,int i,int j) {
    if(e<=i||j<=s||s>=e) return 0;
    else if(i<=s && e<=j) return seg[r];
    else return max(query(r2,s,mm,i,j),query(r2+1,mm,e,i,j));
}
int f(uint x) {
    if(x == 1U) return 1;
    if(x<lim) { if(d[x]) return d[x]; }
    else { if(dp.count(x)) return dp[x]; }
 
    if(x & 1U) {
        if(x<lim) return d[x] = f(x*3+1)+1;
        else return dp[x] = f(x*3+1)+1;
    } else {
        if(x<lim) return d[x] = f(x>>1)+1;
        else return dp[x] = f(x>>1)+1;
    }
}
 
int main() {
    for(int i=1; i <= 1000000; i++) {
        if(d[i]==0) update(1,ss,ee,i,f(i));
        else update(1,ss,ee,i,d[i]);
    }
    int l,r;
    while(scanf("%d%d",&l,&r)!=EOF) {
        if(l<r) printf("%d %d %d\n",l,r,query(1,ss,ee,l,r+1));
        else printf("%d %d %d\n",l,r,query(1,ss,ee,r,l+1));
    }
    return 0;
}