[백준 자바] 14928번(큰 수 (BIG)) - 모듈러 연산

브론즈 5

문제

제연이는 그의 생일(2000년 3월 3일)을 기념해 자신이 가장 좋아하는 수를 20000303으로 나눈 나머지를 구해 그 수만큼 잠을 자기로 했다. 제연이가 얼마나 잠을 잘 수 있을지 구하자.

입력

첫째 줄에 제연이가 가장 좋아하는 수 N이 주어진다. (N ≤ 101,000,000)

출력

N을 20000303으로 나눈 나머지를 출력한다.

 

---

 

728x90

단순히 BigInteger.mod()로 작성하면 시간초과가 뜬다.

모듈러 연산의 (a + b) % c = ((a % c) + (b % c)) % c 성질을 이용하여 큰 수를 작은 부분으로 나누어 처리한다.

import java.io.*;

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String input = br.readLine();
    int mod = 20000303;

    int result = 0;
    for (int i = 0; i < input.length(); i++) {
      result = (result * 10 + (input.charAt(i) - '0')) % mod;
    }

    bw.write(String.valueOf(result));

    bw.flush();
    br.close();
    bw.close();
  }
}

위 공식을 143%7로 예를 들면,

1. result = (0 * 10 + 1) % 7 = 1
2. result = (1 * 10 +4) % 7 = 0
3. result = (0 * 10 + 3) % 7 = 3

결과는 3이 출력된다.