[JAVA] 백준 1629번 : 곱셈

https://www.acmicpc.net/problem/1629

1629번: 곱셈

---

import java.util.Scanner;

public class Main {
    static int C;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A = sc.nextInt(); int B = sc.nextInt(); C = sc.nextInt();
        System.out.println(power(A % C, B));
    }

    private static long power(long a, int b) {
        if (b == 1) return a % C;
        long tmp = power(a, b / 2);
        if (b % 2 == 0)
            return tmp * tmp % C;
        else
            return (tmp * tmp % C) * a % C;
    }
}

💡 수학, 재귀

풀이

• 처음에는 단순 dp를 사용해서 풀었고 그 결과 메모리 초과...
• 재귀 형식으로 시도하던 중, B를 1개씩 줄여나가면 스택오버플로우 발생함
  • 재귀를 효율적으로 덜 호출하는 방법 => return에서 power() * power() 형태로 B/2씩 줄일 수 있음
  • 대신, return에 바로 power 함수를 여러번 호출할 경우, 시간초과 발생할 수 있으므로 power(A, B/2)값을 tmp로 저장한 뒤, return에 사용하는 방식을 쓰자!!
  • B/2 이므로 B가 홀수/ 짝수일 때 경우를 나눠줘야 함
  • 재귀 처음 들어갈 때 매개변수 자리에 A % C로 주기!