글 읽기 - 두 코드의 차이가 궁금합니다

khj0426 1년 전 0

제일 처음 코드가 제가 작성한 코드고 분할정복을 이용해서 풀어봤는데 계속 틀려서, 딴 분들의 코드를 보니깐

제일 처음 함수를 호출할 떄 나머지 연산을 한 부분이 보여서 그 부분만 바꿨는데 맞았습니다..

제일 처음 함수 호출 시 나머지 연산을 해야 하는 이유가 궁금합니다..!

//처음 코드

#include <iostream>
#define MOD 1000000007
using namespace std;
typedef long long ll;
 
ll calculate(ll a,ll x){
    if(x == 0){
        return 1;
    }
    else if(x == 1){
        return a;
    }
    else if(x%2 != 0){
        return calculate(a,x-1) % MOD * a % MOD;
    }
    else if(x%2 == 0){
        return calculate(a,x/2) % MOD * calculate(a,x/2) % MOD;
    }
}
int main(void){
    ll A;
    ll X;
    cin >> A >> X;
    /*나머지 연산 X */
    cout << calculate(A,X) % MOD;
}


//맞은 코드

#include <iostream>
#define MOD 1000000007
using namespace std;
typedef long long ll;
 
ll calculate(ll a,ll x){
    if(x == 0){
        return 1;
    }
    else if(x == 1){
        return a;
    }
    else if(x%2 != 0){
        return calculate(a,x-1) % MOD * a % MOD;
    }
    else if(x%2 == 0){
        return calculate(a,x/2) % MOD * calculate(a,x/2) % MOD;
    }
}
int main(void){
    ll A;
    ll X;
    cin >> A >> X;
    
    /*나머지 연산을 처음에 해야 하는 이유..? */
    cout << calculate(A % MOD,X) % MOD;
}

bamgoesn 1년 전 1

일반 근본적으로는 오버플로우 문제인데, 연산자 우선순위때문에 그 문제가 숨겨져 있습니다.

*와 %는 연산자 우선순위가 같습니다. 따라서 *와 %가 괄호 없이 사용되면 왼쪽에서 오른쪽으로 순서대로 계산됩니다.

틀린 코드의 일부분인 calculate(a,x-1) % MOD * a % MOD;를 보시면, *와 %이 혼재하므로 왼쪽부터 오른쪽으로 순서대로 계산됩니다. 이때 calculate(a, x-1) % MOD는 MOD 미만의 수겠지만, 그 다음에 a를 곱하는 과정에서 a가 너무 크면 오버플로우가 발생할 수 있습니다. a는 최대 1e18이므로 이는 long long의 범위도 넘어버립니다. 그래서 오버플로우가 발생하고 오답을 출력하게 됩니다.

괄호만 좀 쳐서 (calculate(a,x-1) % MOD) * (a % MOD);와 같이 바꾸면 오버플로우 문제가 없어집니다. 그 아래 조건분기도 동일하게 괄호를 쳐주시면 됩니다.

khj0426 1년 전 0

답장이 늦어버렸네요... 연산자 우선순위 문제였네요...감사드립니다!

많이 배워갑니다!-!

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

문제

문제

출처

ICPC

두 코드의 차이가 궁금합니다

khj0426 1년 전 0

bamgoesn 1년 전 1

khj0426 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말