인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

기저사례 부분, 그리고 go()라는 값을 변수에 할당해서 재사용하는 부분이 틀린 것 같습니다.

제가 좀 다듬어봤습니다. ㅎㅎ 참고부탁드립니다.

#include <bits/stdc++.h>
using namespace std;

long long a, b, c;

long long go(long long a, long long b) {
    if (b == 0) return 1;
    long long half = go(a, b / 2);
    long long ret = (half * half) % c;
    if (b % 2) ret = (ret * (a % c)) % c;
    return ret;
}

int main() {
    cin >> a >> b >> c;
    cout << go(a, b);
    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 대기업목표님, 문의해 주셔서 감사합니다.

작성하신 질문을 보니 C++에서 곱셈을 다루는 문제를 해결하시는데 어려움을 겪고 계신 것 같습니다. 이 문제의 주요 이슈는 아마도 연산 도중에 발생할 수 있는 범위 초과 문제일 것입니다. 나눗셈을 통해 수치를 줄이려는 시도를 하고 있는지 확인하는 것이 중요합니다. 특히, 수가 커질 경우 long long의 범위를 초과할 수 있습니다.

비슷한 질문이 있어 링크를 드리며 설명을 덧붙입니다:

1. 1-N 코드 질문있습니다

   • 해당 질문에서는 20억의 대규모 연산이 long long의 범위를 초과할 수 있으며, pow 함수의 시간복잡도가 관련된 문제일 수 있음을 설명하고 있습니다.
     
   • pow 함수가 O(log B)의 시간복잡도를 가진다는 점도 염두에 두셔야 합니다. pow 함수의 사용법에 대해서도 코드를 꼭 검토해 보세요.
     

2. 코드 관련 질문입니다!

   • 코드에서 곱셈 후 즉시 모듈로 연산을 하지 않아 범위 문제가 발생할 수 있음을 설명합니다. 중간 계산 값이 int나 long long의 범위를 넘는지 확인하는 것이 중요합니다.
     

3. 출력 오류 질문있습니다

   • 출력이나 값을 다루는 도중에 범위가 초과되지 않도록 아스키코드와 유사한 범위를 염두해 두고 처리하는 것이 필요합니다.
     

코드의 로직을 개선하거나 모듈로 연산(나머지 연산)을 적절히 사용하여 연산 결과를 작은 수로 유지하는 전략을 고려해 보세요. 그러면 문제 해결에 도움이 될 것입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.