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

아 찾았습니다. 이렇게 하시면 됩니다.

이렇게 한번 제출해보시겠어요?

(long long 처리를 안해서 그런 것같습니다.)

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

ll a, b, c;

ll go(ll b) {
    if (b == 1) return a % c;
    else if (b == 2) return (a * a) % c;

    ll ret = go(b / 3); 
    ret = ((ret * ret) % c * ret) % c; 

    if (b % 3 == 1) ret = (ret * a) % c;
    else if (b % 3 == 2) ret = (ret * a % c * a) % c;

    return ret;
}

int main() {
    cin >> a >> b >> c;
    cout << go(b) << "\n";
}

안녕하세요 kkh님 ㅎㅎ

1. 안되는 이유가 연산코스트가 줄지만 ret=(ret*ret*ret)%c; 에서 ret에서 저장할수있는 값을 초과해서일까요?

>> 음.. 어차피 모듈러 연산을 해서 그부분은 괜찮은 것 같은데 틀렸다고 뜨네요..

일단 좀 다듬은 코드는 다음과 같은데요.

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

int a, b, c;

ll go(int b) {
    if (b == 1) return a % c;
    if (b == 2) return (a * a) % c;

    long long ret = go(b / 3);
    ret = ((ret * ret) % c * ret) % c; 

    if (b % 3 == 1) ret = (ret * a) % c;
    else if (b % 3 == 2) ret = (ret * a % c * a) % c;

    return ret;
}

int main() {
    cin >> a >> b >> c;
    cout << go(b) << "\n";
}

3분할로 해도 1, 2 경우의 수 따져서 될 것 같은데... 해당 부분은 좀 더 생각해보고 다시 답변 달겠습니다. :)

2. 3등분도 아니고 4등분도 아니고 2등분을 선택하신 이유에 대해서 궁금합니다!

    

    

    

    

    

   >> 분할정복자체가 어떠한 로직을 2개로 나눠서 하는 것이라 2로 했습니다.

감사합니다.