[Algorithm / JAVA] 백준 1629번 곱셈

key word : 곱셈, n제곱, mod, 나머지

문제

자연수 A를 B번 곱한 수를 C로 나눈 나머지를 구하면 된다. 여기서 주의할 점은 A, B, C가 각각 2,147,483,647 이하의 자연수라는 점이다.

아이디어

문제에 대한 접근법, 힌트는 바킹독님의 유튜브 강의에서 얻었다.

나머지를 구하는 방법에는 다음과같은 것들이 있다고 한다.

1. 첫 번째 수를 k로 나눈 나머지를 다음 수와 곱하고 또 그걸 k로 나누면 결국 첫 번째 수와 두 번째 수의 곱을 k로 나눈 나머지의 값과 같은 값이 나오게 된다.
   증명을 따로 찾아보진 않았지만 상식적으로 충분히 이해가 가능하다. 나누어진 수(몫)은 어차피 나누어지는 부분이고, 마지막까지 남는 수가 나머지가 되는 원리이다.

2. 위의 이야기와 연결되는 이야기로 a의 2n제곱을 k로 나눈 나머지도 쉽게 구할 수 있다. a의 2n제곱은, a의 n제곱의 제곱이므로, a의 n제곱을 k로 나눈 나머지를 제곱한 후 또 다시 k로 나눠주면 a의 2n제곱의 나머지를 구할 수 있다.

구현

위와같은 특성때문에 이 문제는 점화식을 세워 접근하면 재귀를 이용해 풀 수 있다. 내가 재귀 함수를 구성한 방식은 다음과 같다.

1. A의 B제곱이니 최대 B번 반복할 것이고, base condition은 B가 0 or 1일 때로 정하면 될 것이다.
2. base condition에 도달했을 때 반환되는 값은 마지막으로 전달된 A 값을 C로 나눈 나머지여야 반환을 거치며 A의 거듭제곱에 대한 C로 나눈 나머지가 될 것이다.
3. 2k일 때와 2k + 1일 때를 나누어 생각해야 하므로 b % 2 == 0의 조건문이 들어가고, 각각 다른 인자를 넣는 재귀 호출을 진행해야 할 것이다.

4. 2k일 때에는 a의 b / 2 제곱을 c로 나눈 나머지의 제곱을 c로 다시 나눈 나머지가 필요하며, 2k + 1일 때에는 a의 b - 1 제곱을 c로 나눈 나머지에 a를 다시 곱한 후 c로 나눈 나머지가 필요하다.
   
   이러한 생각을 바탕으로 자바를 이용해 구현한 결과이다.

   import java.io.BufferedReader;
   import java.io.InputStreamReader;
   import java.io.IOException;
   
   public class PowerMod {
       static long A, B, C;
   
       public static void init() throws IOException{
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           String[] str = br.readLine().split(" ");
   
           A = Integer.parseInt(str[0]);
           B = Integer.parseInt(str[1]);
           C = Integer.parseInt(str[2]);
       }
   
       public static long findMod(long a, long b, long c) {
           if(b == 1)
               return a % c;
   
           if(b == 1)
               return a % c;
   
           if(b % 2 == 0) {
               long val = findMod(a, b/2, c);
               val = val * val % c;
               return val;
           }else {
               long val = findMod(a, b - 1, c);
               return a * val % c;
           }
       }
   
       public static void main(String[] args) throws IOException{
           init();
           System.out.println(findMod(A, B, C));
       }
   }
   

   위 영상을 보면 이것과는 좀 다른 코드가 나오는데, 사실 그 코드가 b가 홀수일 때 함수 호출을 한 번씩 덜 해도 되는 구조여서 조금 더 빠르긴 하다. 그래도 재귀 함수 자체를 많이 구현해보지 않았는데 스스로 이만큼 구현했다는 것이 뿌듯했다.

오류

1. int overflow

   가장 중요한 부분인데 지키지 않아 맞왜틀을 혼자서 엄청 외쳤다..

   A, B, C가 각각 약 21억까지 나올 수 있다는 것은 그것들의 곱은 훨씬 더 클 수도 있다는 것인데,,, 그냥 반가운 숫자를 본 나머지 변수 타입을 int로 지정해버렸다. long으로 바꿔서 실행해주니 잘 동작했다.

   알고리즘 문제를 풀 때 메모리 사이즈나 시간복잡도를 생각하는 것은 정말 몇번씩 생각하고 또 생각해도 과하지 않은 것 같다. 진짜 다 풀어놓고 overflow 때문에 맞왜틀 외치고 있던거 생각하면 아직 멀었다는 생각밖에 안든다 ㅠ 앞으로는 타입 체크, 메모리 사이즈 체크 한 번 씩 더 해야지.