백준BOJ/JAVA : 14928번 큰 수 (BIG)

14928번 : 큰 수 (BIG) 원본

알고리즘 분류

• 수학
• 사칙연산
• 임의 정밀도 / 큰 수 연산

문제

제연이는 그의 생일(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

해당 법칙을 소스로 표현하면 왼쪽부터 자릿수를 늘려가면서 나머지를 구하였다.

1. for (int i = 0; i < num.length(); i++)
   • 입력 자릿수만큼 반복
2. remainder *= 10
   • remainder의 10만큼 곱함
3. remainder += (num.charAt(i) - '0')
   • remainder에 i번째 자릿수를 더함
4. 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();
    }
}

참고

14928 - 큰 수 (BIG) (C++)