[자바, 파이썬] 백준 14928 - 큰 수 (BIG) (boj java python)

문제 : boj14928

 

  문제 자체는 아주 심플하다. 문제 그대로 N을 20000303으로 나눈 나머지를 출력해주면 된다. 문제는 큰 수를 지원해주는 언어에 따라 난이도가 매우 다르다는 점이다. 파이썬의 경우 큰 수를 지원하므로 그냥 n을 입력받아 나머지를 출력만 해주면 끝난다(물론 오래걸린다). 자바의 경우엔 BigInteger로 큰 수를 지원해주긴한데, 시간초과로 통과가 안된다ㅋㅋㅋ

 

  사실상 파이썬으론 엄청 쉽고, 나머지 언어론 큰 수를 지원해줘도 시간초과가 날 것 같다. 아무튼 그럼 파이썬은 풀이라고 할게 없으니 자바코드를 풀이로 작성해보겠다.

 

  이걸 파이썬처럼 단순히 푸는게 아니라 직접 풀려면 결국 나머지 연산(%)에 대한 수학적 지식이 좀 필요하다. 나머지 연산에도 분배법칙이 있는데 덧셈에 대해 다음과 같다. (M은 나누는 수)

 

  그럼 N = abcd 라고 할 때(예를들어 N이 1234라면 a=1, b=2, c=3, d=4),

N = abcd = a*1000 + b*100 + c*10 + d 라고 할 수 있다. 대충 a*1000을 a000 이라 표현해보면,
abcd % mod은 분배법칙에 따라 (a000%mod+b00%mod+c0%mod+d%mod)%mod 이다.

 

  따라서 cur이라는 변수에 최종 출력할 답을 구한다고 하면, 그냥 N을 큰 자리수부터 (즉, String으로 봤을 때 가장 좌측의 수 부터) 쭉 보면서 이하의 로직을 계속해주면 된다. 그럼 cur은 int 타입으로도 충분히 연산이 가능해진다.

1. cur *= 10

2. cur += [N에서 현재 보고 있는 수]

3. cur %= 20000303

 

여기서 '1'의 과정은, 큰 수 연산을 하지 않기 위해 사용된 부분이다. 즉 위에 설명대로 하려면 N의 가장 왼쪽 수에 대해  a*1000000...000000을 해줘야 하는데, 큰 수라는게 결국 수를 String으로 표현하는 방식이므로 이미 여기서 자리수만큼 시간복잡도가 발생하게 되므로 느려질 수 밖에 없다. 따라서 '1'의 과정에서 이전에 구한 값을 *10 해줌으로써 매번 병렬적으로 *10을 해서 결론적으론 a*1000000...000000 을 해주는것과 마찬가지가 된다.

 

... 결론은 이 문제가 브론즈5인 이유는 파이썬에서 엄청 쉽게 통과되기 때문이다. 시간제한이 0.5초 정도였으면 파이썬도 통과못하니 실버 하위권쯤 갔을거라 본다. (이하 코드에서 자바로 직접 짠건 188ms, 파이썬으로 단순 계산한건 5976ms)

 

코드(자바) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private final static int MOD = 20000303;
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String n = br.readLine();
        int cur = 0;
        for (int i = 0; i < n.length(); i++) {
            cur*=10;
            cur+=n.charAt(i)-'0';
            cur%=MOD;
        }
        System.out.println(cur);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

코드(파이썬) : github

import sys
input = sys.stdin.readline
n = int(input())
print(n % 20000303)