[14928] [Java] 큰 수 (BIG)

https://www.acmicpc.net/problem/14928

14928번: 큰 수 (BIG)

 

추가 개념

해당 문제는 "나머지 연산 분배 법칙"이라는 것을 사용해야 한다.
그 근거로는, 단순히 BigInteger 클래스를 사용하면 시간 초과가 나기 때문. 분배법칙은 아래와 같다.

(A + B) % N = ((A % N) + (B % N)) % N

나머지 연산 분배 법칙의 예시는 아래와 같다.
(그림 출처) : https://blex.me/@laetipark/%EB%B0%B1%EC%A4%80bojjava-14928%EB%B2%88-%ED%81%B0-%EC%88%98-big

필자는 이 법칙에 대해 처음 접해봤기에 코드 풀이를 보지 않고 해당 법칙만 보고 30분 고민 후 풀었다.

 

문제 접근

문자열을 입력 후 첫 인덱스부터 시작하여 나머지를 구하도록 한다.
(이때 다음 인덱스에서 계산할 때 바로 전의 계산 값에 10을 곱한 후 가져온다.)
char 형을 int 형으로 변환하는 것도 인지해야 한다.

 

풀이 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String num = sc.nextLine();
        int number = 0;
        for(int i = 0; i < num.length(); i++){
            char charAt = num.charAt(i);
            int toInt = charAt - '0'; // char형을 int으로 변환
            int ten = (toInt + 10 * number) % 20000303; // 나머지 출력
            number = ten;
        }
        System.out.println(number);
    }