BRUTEFORCE 문제 질문 드립니다.

  • sancho
    sancho

    BRUTEFORCE 풀고 있는데 시간초과가 자꾸 나오네요.

    끄적끄적 해서 다음과 같이 점화식을 세웠습니다.

    solve(start,end,n) =
    solve(start,(start+end-1)/2,n) +
    (n^((end-start+1)/2))*solve(start,(start+end-1)/2,n)

    코드는 아래와 같이 작성했는데..
    답은 맞게 나오는데 시간초과로 패쓰를 못하고 있네요;;
    최적화 포인트가 더 있는건가요?
    미리 감사드립니다.

    #include <iostream>
    
    using namespace std;
    const int MOD = 1000000007;
    
    // 최소자리수 start, 최대자리수 end, 문자 수 n 일때,
    // 모든 가짓수를 구한다.
    long long solve(int start, int end, int n)
    {
        // 기저사례
        if (n == 1) return end - start + 1;
        if (start > end) return 0;
        if (start == end) {
            long long ret = 1;
            for (int i = 0; i < start; i++)
                ret = (ret * n) % MOD;
            return ret;
        }
    
        // 갯수가 홀수인 경우는 맨 뒤를 하나 제낀다.
        bool odd = false;
        if ((end - start + 1) % 2 == 1) {
            --end;
            odd = true;
        }
    
        // 반으로 나누고 앞에꺼 계산
        // solve(start, (start + end - 1) / 2)
        long long ret = 0;
        int mid = (start + end - 1) / 2;
        ret = solve(start, mid, n);
        ret %= MOD;
    
        // 뒤에꺼는 앞에꺼 계산 결과를 이용해서 구한다.
        // (n ^ ((end - start + 1) / 2)) * solve(start, (start + end - 1) / 2)
        long long ret2 = 1;
        int mid2 = (end - start + 1) / 2;
        for (int i = 0; i < mid2; i++)
            ret2 = (ret2 * n) % MOD;
        ret += ret2 * ret;
        ret %= MOD;
    
        // 홀수인 경우에 처음에 제낀것을 계산하여 더한다.
        if (odd) {
            for (int i = mid2; i < end + 1; i++)
                ret2 = (ret2 * n) % MOD;
            ret += ret2;
            ret %= MOD;
        }
    
        return ret;
    }
    
    int main(int c, char **v)
    {
        ios_base::sync_with_stdio();
        int C;
        cin >> C;
        while (C--) {
            int A, B, N;
            cin >> A >> B >> N;
            cout << solve(A, B, N) << endl;
        }
        return 0;
    }
    


    9년 전
2개의 댓글이 있습니다.
  • WeissBlume
    WeissBlume

    a^n을 O(logn)에 계산할 수 있습니다.
    http://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/


    9년 전 link
  • sancho
    sancho

    오오 단번에 패스했습니다.
    저 생각을 못했네요.. 감사합니다.


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.