728x90
문제
정수 A, B, C가 주어졌을 때
A를 B번 곱한 값을 C로 나누었을 때 몫을 구하라
접근 방식
문제 자체는 엄청 간단한 문제지만 시간제한과 메모리 제한이 걸려있기 때문에
반복문이나 재귀로 하나하나 다 곱하고 나누면 통과할 수 없는 문제다.
(값의 표현 범위를 벗어나기도 한다)
반복문으로도 풀 수 있고 재귀로도 풀 수 있는 문제지만
재귀를 공부할 겸 재귀로 풀어보았다.
우선 반복문으로 풀면 메모리 초과가 발생할 일은 없지만
재귀로 풀 때는 조심해야 할 부분이 있는데
재귀 호출을 B만큼 반복하면 호출 스택에 그만큼 쌓여
B의 값이 큰 경우에는 메모리가 초과되기 때문에
재귀 호출을 최대한 줄이는 방식으로 풀어야 한다.
(x ^ n) * (x ^ n) = x^2n
위와 같은 법칙을 생각해서 풀면 되는데
만약 10의 10승을 구한다면 10의 5승까지만 구해도
10의 5승을 제곱하면 10의 10승이기 때문에
계산 횟수를 줄일 수 있다.
(9 ^ 7) % 7
9 2
18 4
36 1
9 2
18 4
36 1
9 2
18 4
또한 값을 계속 곱해주다 보면 int나 long 타입으로
표현할 수 있는 값의 범위를 벗어나게 되는데
위의 계산 순서에서 알 수 있듯이
그때 그때 나눠준 후에 제곱을 해도
몫은 항상 같기 때문에
값의 범위를 벗어나는 것을 방지할 수 있다.
풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
long a = Long.parseLong(st.nextToken());
long b = Long.parseLong(st.nextToken());
long c = Long.parseLong(st.nextToken());
System.out.println(calculate(a, b, c));
}
private static long calculate(long a, long b, long c) {
if (b == 1) return a % c;
long result = calculate(a, b/2, c);
result = (result * result) % c;
if (b % 2 == 0) {
return result;
}
return (a * result) % c;
}
}
'Java > Algorithms' 카테고리의 다른 글
[프로그래머스] 최소직사각형 (1) | 2023.10.24 |
---|---|
[백준] 11729번 : 하노이 탑 이동 순서 (1) | 2023.10.14 |
[백준] 11728번 : 배열 합치기 (0) | 2023.10.12 |
[백준] 10026번 : 적록색약 (0) | 2023.10.11 |
[백준] 1012번 : 유기농 배추 (0) | 2023.10.11 |