📜 문제
- 2,147,483,647 이하의 자연수 a, b, c가 주어진다.
- a를 b번 곱한 수를 c로 나눈 나머지를 출력한다.
재귀를 이용해 푸는 문제이다.
간단해 보이지만, 메모리 제한과 시간 제한이 심상치 않다.
문제를 읽고 넘 간단해서 엥? 하고 뚝딱뚝딱 코드를 짜고 돌렸는데, 메모리 초과 에러가 발생했다.
2,147,483,647 이하의 자연수는 오버플로우에 걸리기 딱 좋다..
결국 다른 분의 문제 풀이를 보고 수학 공식을 이용해서 풀어야 함을 알았다.
공식
1. 지수 법칙
2. 모듈러 연산
문제 예제인 a=10, b=11, c=12인 경우를 예로 들자.
우리는 10의 11승인 10¹¹을 구해야 한다.
| 값 | 지수 법칙 |
|---|---|
| 10¹¹ | 10⁵ * 10⁵ * 10¹ |
| 10⁵ | 10² * 10² * 10¹ |
| 10² | 10¹ * 10¹ |
따라서 우리는 10⁵, 10² 만 구하면, 찾아야 하는 10¹¹을 구할 수 있다.
✍ 부분 코드 설명
변수 선언
public static void main(String[] args) throws IOException {
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long n = Long.parseLong(st.nextToken());
long pow = Long.parseLong(st.nextToken());
long div = Long.parseLong(st.nextToken());
...n: 곱하는 수 (a)
pow : 곱하는 횟수 (b)
div: 나누는 수
거듭 제곱 구하기
public static long mul(long n,long pow, long div){
if(pow==1) return n%div;
long tmp = mul(n, pow/2, div);
// 값이 홀수인 경우
if(pow%2==1) {
return (tmp*tmp%div)* n%div;
}
// 짝수인 경우
return tmp*tmp %div;
}여기서 눈여겨 봐야하는 점은 return문이다.
지수 법칙을 이용한 건 인정하지만 왜 모듈러 연산을 이용해야 할까?
그것은 문제에 주어진 a, b, c는 2,147,483,647 이하의 자연수라는 조건때문이다.
int 자료형의 최대값은 문제에 제기된
2,147,483,647 (2³¹-1)이다.
long 자료형의 최대값은9,223,372,036,854,775,807 (2⁶³-1)이다.
tmp 값이 2,147,483,647인 경우, tmp * tmp 값은 long 자료형을 초과하지 않지만, n이 2,147,483,647이라면 말이 달라진다.
pow 값이 홀수인 경우 우리는 tmp * tmp * n 을 수행해야 하는데,
그렇게 되면 long 자료형의 최댓값을 가뿐히 초과한다.
그래서 우리는 모듈러 연산을 수행해서 오버플로우가 발생하지 않도록 하는 것이다.
위에 설명한 모듈러 연산에서 a 값을 tmp * tmp, b 값을 n이라고 칭하면
// 모듈러 연산
(a * b) % c = (a % c * b % c) % c
(tmp * tmp * n) % div
= ((tmp * tmp % div) * (n % div)) % div
// tmp * tmp % div = (tmp * tmp % div) % div) 와 같다.
= (((tmp * tmp % div) % div) * (n % div)) % div
// 모듈러 연산: (tmp * tmp % div) % div를 한 이유
= ((tmp * tmp % div) * n ) % div모듈러 연산을 사용하면, pow가 홀수인 경우 오버플로우가 발생하지 않는다.
🍳 전체 소스 코드
package Algorithm.Recursion;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class N_1629 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long n = Long.parseLong(st.nextToken());
long pow = Long.parseLong(st.nextToken());
long div = Long.parseLong(st.nextToken());
System.out.println(mul(n,pow,div));
}
public static long mul(long n,long pow, long div){
if(pow==1) return n%div;
long tmp = mul(n, pow/2, div);
if(pow%2==1) {
return (tmp*tmp%div)* n%div;
}
return tmp*tmp %div;
}
}
✨ 결과
지수 법칙이니 모듈러 연산이니... 어려웠다.
처음에 쉬운데? 하고 접근하고 결국엔 풀지 못하니까 더 타격이 컸다.
조금 좌절한 후 글로 작성하니 애매한 부분도 완벽히 씹을 수 있었다.
재귀.. 너도 갖고 싶어..
