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

백준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++)

이 글이 도움이 되었나요?

신고하기
0분 전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.