백준 1629 (재귀함수)

1629번: 곱셈

과정

• 일단.. 문제가 너---무 단순해서 뭘 원하는지 파악하기에 당황했다.
• 단순히 A를 B만큼 곱하고, C로 나눈 후 나머지를 구하는건데, A를 B만큼 곱하는 과정에서 
  
  1. 뻔하게 A를 B만큼 for문으로 곱하면 100000% 시간초과에 걸릴 것 같고..
  2. C로 나누는 거에 뭐가 있나? 싶기도 하고..
• 일단, 시간 초과 관련해서는 아래와 같은 코드를 작성해줌으로서 조금 완화된다는 것을 알고 있다.

ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);

• 거듭제곱에 대한 또다른 수식이 있는지 찾아봐야 한다. 

거듭제곱 관련 수식

• 위 사진을 보면 지수를 반으로 계속 쪼개는걸 알 수 있다. 즉, 지수에 해당하는 B값의 짝, 홀을 파악한 후, A를 곱해주면 된다.
• 이런 식으로 할 경우, 아마 재귀함수와 비슷하게 O(N)이 걸릴 것을 O(logN)으로 해결할 수 있다.

+추가+

문제를 보면 자연수 A, B, C가 모두 2,147,483,647 이하의 자연수 라고 명시되어 있다.

왜 하필 저 큰 숫자인가 찾아보니 int의 최대값이 2,147,483,647 이다. 즉, ABC는 int가 아닌 longlong으로 형을 정해주는게 안전해 보인다.

코드

#include <iostream>

using namespace std;

long long A = 0;  // 곱할 자연수

long long B = 0;  // 곱해질 횟수

long long C = 0;  // 나눌 자연수

long long answer = 0;   // 정답 (A^B%C)

long long power (long long b)

{

    // 0번 곱할 경우 A, C값과 상관없이 1이다.

    if (b == 0)

        return 1;

    // B가 1이면 그냥 A%C 해서 나머지를 구하면 된다.

    if (b == 1)

        return A % C;

   

    long long k = power(b / 2) % C;

    // 지수가 짝수면

    if (b % 2 == 0)

        return k * k % C;

    // 지수가 홀수면

    else

        return k * k % C * A % C;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(nullptr); cout.tie(nullptr);

    cin >> A >> B >> C;

    answer = power(B);

    cout << answer;

    return 0;

}

 

코드를 보면서, 작성하면서 의문이 들 수 있는 점을 정리해본다.

 

1. 어차피 answer 자체는 int형 안에 들어가는데(나머지이므로) 왜 long long을 사용하는가?
: 원래는 power()안에 k대신 사용하려고 했다. 하지만, 정답을 받는 변수로 중간에 바꿨고, 통일성을 주기 위해 그냥 long long을 사용하게 되었다.

 

2. power()의 return 값을 보면, 왜 나머지값에 A%C를 곱하는가? 그냥 나중에 한번에 나눠서 나머지를 구하면 안되는가?

: 나도 그랬다.. 초기 코드는 K * K * A % C로 했는데, 이렇게 하다보니, K * K * A 부분이 long long 범위를 벗어날 수 있다는 생각이 들었다. 그래서 먼저 짝수일 경우 return 값처럼 계산 후 거기에 A%C를 곱하게 되었다.