문제
https://www.acmicpc.net/problem/1629
1629번: 곱셈
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
www.acmicpc.net
풀이
아래와 같이 짜면 시간/메모리 초과가 발생한다.
public static long recur(long a, long b, long c){
if(a==1 || b==1) return a;
return a * recur(a, b-1, c) % c;
}
recur(a*a, b/2, c)로 호출하여 함수 호출 횟수를 줄이는게 핵심이다.
overflow가 발생하지 않도록 여러 곳에 c로 mod연산을 해야한다.
b가 1인 조건일 때 mod연산을 누락해서 한참 헤멨다. (96%에서 틀림 찍힘)
소스코드
package divideconquer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ1629 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
System.out.println(recur(a, b, c));
}
public static long recur(long a, long b, long c){
if(a==1 || b==1) return a%c;
a = a%c;
if(b%2 == 0){
return recur(a*a%c, b/2, c) % c;
} else {
return a * recur(a*a%c, b/2, c) % c;
}
}
}
'💡Problem Solving > BOJ' 카테고리의 다른 글
[BOJ 7569] 토마토 3차원 (Java) (0) | 2021.11.19 |
---|---|
[BOJ 7576] 토마토 (Java) (0) | 2021.11.19 |
[BOJ 1780] 종이의 개수 (Java) (0) | 2021.11.17 |
[BOJ 1992] 쿼드트리 (Java) (0) | 2021.11.17 |
[BOJ 2630] 색종이 만들기 (Java) (0) | 2021.11.16 |