백준 알고리즘 15829번 자바

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

15829번: Hashing

 

이 문제는 모듈러 연산 법칙을 알아야 한다.

1. (a + b) mod n = {(a mod n) + (b mod n)} mod n
2. (a - b) mod n = {(a mod n) - (b mod n)} mod n
3. (a * b) mod n = {(a mod n) * (b mod n)} mod n

 

이 식을 보고 모듈러 연산 법칙 중 3번만 선택해서 문제를 풀면 틀린다..

3번만 이용하게 되면 마지막에 왜 나머지를 한번 더 계산해야하는지 이해하지 못한다..

 

1번과 3번을 같이 사용해야 한다.

 

왜 1번과 3번을 같이 사용해야하는지 알아보자.

해석

위 식을 풀어서 쓰면

(a0r0 + a1r1 + a2r2 +a3r3 ...) mod M 이 된다.

여기서

1번 모듈러 연산 법칙을 사용해야 한다.

 

간단히 a0r0과 a1r1만 사용해보자.

(a0r0 + a1r1) mod M 이 된다.

이 식을 바꾸면

{(a0r0 mod M) + (a1r1 mod M)} mod M

이렇게 된다.

(a0r0 mod M) 과 (a1r1 mod M)을 보면 3번 모듈러 연산 법칙이다.

이 식을 바꾸면

{({(a0 mod M) * (r0 mod M)} mod M) + ({(a1 mod M) * (r1 mod M)} mod M)} mod M

각 각 계산할 때에도 나머지를 계산해줘야하고 마지막에 나머지를 한번더 계산해야 한다

이것을 코드로 옮겨보자.

 

 

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

public class A15829 {
    static final int MU = 1234567891;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(br.readLine());
        String in = br.readLine();
        long sum = 0;
        long r = 1;
        for (int i = 0; i < len; i++) {
            sum += (((in.charAt(i) - 'a' + 1)%MU) * r)%MU; //각각 계산할 때에도 나머지를 구한다
            r = (r*31)%MU;
        }
        System.out.println(sum%MU); //마지막에도 나머지를 구한다
        br.close();
    }
}