글 읽기 - 어디가 틀렸는지 모르겠어 질문올립니다!

audrn31 2년 전 0

제 로직은 양쪽에 있는 거듭제곱수들을 이용해서 재귀적으로 cost를 구해나가는 식이고, NUM값 이하인 경우 memoization을 했습니다!

double 관련해서 생기는 오류일까요? 계속 찾아봤는데 어디서 틀렸는지 찾기 어렵네요..

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

typedef long long int ll;
const ll NUM = 1e6, MAX_NUM = 1e18;
ll cost[NUM+5];

// k < 64
ll smallerSquare(ll x, int k){
    // n^2+k -> n^2
    return pow((ll)(ceil(pow(x, 1.0/k))-1), k);
}

ll biggerSquare(ll x, int k){
    // n^2+k -> (n+1)^2
    ll n = (ll)ceil(pow(x, 1.0/k));
    if(log(pow(n,k)) > log(pow(10,18)*2.1)){
        return smallerSquare(x, k);
    }
    return pow(n, k);
}

ll deriveCost(ll x){
    if(x < NUM && cost[x] != -1){
        return cost[x];
    }
    ll res = MAX_NUM;
    for(int k=2; k<=63; k++){
        ll a = smallerSquare(x, k), b = biggerSquare(x, k);
        ll imsi_res =
            (a<b) ? min(x-a+1+deriveCost((ll)pow(a, 1.0/k)), b-x+1+(ll)deriveCost(pow(b, 1.0/k))) 
            : x-a+1+deriveCost((ll)pow(a, 1.0/k));
        
        res = min(res, imsi_res);
    }
    if(x<NUM){
        cost[x] = res;
    }
    return res;
}

int main()
{
    // freopen("input.txt", "r", stdin);
    ll x;
    scanf("%lld", &x);
    memset(cost, -1, sizeof(cost));
    cost[1] = 0, cost[2] = 1, cost[3] = 2, cost[4] = 2;
    printf("%lld", deriveCost(x));
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠어 질문올립니다!

audrn31 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말