알고리즘 분류
- 수학
- 사칙연산
- 임의 정밀도 / 큰 수 연산
문제
제연이는 그의 생일(2000년 3월 3일)을 기념해 자신이 가장 좋아하는 수를 20000303으로 나눈 나머지를 구해 그 수만큼 잠을 자기로 했다. 제연이가 얼마나 잠을 잘 수 있을지 구하자.
입력
첫째 줄에 제연이가 가장 좋아하는 수 N이 주어진다. (N ≤ 10^1,000,000)
출력
N을 20000303으로 나눈 나머지를 출력한다.
풀이
import java.math.BigInteger;
import java.util.Scanner;
public class Baek14928_1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
BigInteger n = scanner.nextBigInteger();
BigInteger m = new BigInteger("20000303");
System.out.println(n.remainder(m));
scanner.close();
}
}
10의 100만 제곱의 B의 숫자를 입력 받아 계산한다고 해서
BigInteger 클래스를 이용했는데 시간 초과로 실패한 것을 확인하였다.
클래스를 이용해서는 불가능한 것 같아서 나머지 연산 분배 법칙을 이용하였다.
나머지 연산 분배 법칙
- (A + B) % N = ((A % N) + (B % N)) % N
해당 법칙을 소스로 표현하면 왼쪽부터 자릿수를 늘려가면서 나머지를 구하였다.
- for (int i = 0; i < num.length(); i++)
- 입력 자릿수만큼 반복
- remainder *= 10
- remainder의 10만큼 곱함
- remainder += (num.charAt(i) - '0')
- remainder에 i번째 자릿수를 더함
- remainder %= 20000303
- remainder의 20000303 나머지를 구함
소스 코드
import java.util.Scanner;
public class Baek14928_2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String num = scanner.next();
long remainder = 0;
for (int i = 0; i < num.length(); i++) {
remainder = (remainder * 10 + (num.charAt(i) - '0')) % 20000303;
}
System.out.println(remainder);
scanner.close();
}
}