[BOJ/JAVA] 26008. 해시해킹

문제 설명

문제 링크

접근 방법

모듈러 연산의 덧셈 분배법칙을 활용하여 해시 함수를 전개하면,
$h(P) = (P_0\cdot A^0)\bmod M + (P_1\cdot A^1)\bmod M +…+(P_{N-1}\cdot A^{N-1})\bmod M$으로 나타낼 수 있다. 각각의 값은 $0\sim M-1$을 가지며, $M$개의 값을 가지는 $N$개의 수로 조합하는 것이 전체 경우이다. 그래서 전체 경우의 수가 $M^N$개인 것이다. $(P_0\cdot A^0)\bmod M$와 나머지 부분의 합도 마찬가지이다. 왼쪽 값이 0인 경우에도 오른쪽 값의 범위는 같으며, 이를 통해 각 해시값의 경우의 수는 모두 같다고 생각할 수 있다. (수학적으로 증명...은 하지 못해서 생각할 수 있다고 쓰겠다.) 즉 $M$개의 값 중 하나를 가지는 전체 경우는 $M^N/M = M^{N-1}$개이며, 이것이 정답이다. 여기까지 왔으면 다 온줄 알았는데, 하나의 난관이 더 있다. 제곱수이므로 수가 굉장히 커져 long 정수형의 범위도 넘어가는 아주 큰 값이 나올 수 있다. 단순하게 Math.pow() 메소드로는 구할 수 없다는 말이다. 여기에선 모듈러 연산의 거듭제곱의 법칙을 활용한다.

$M$을 하나씩 곱해준 뒤 나머지를 구해도 전체 나머지를 구할 수 있다는 의미이다. 이를 응용하여 반복문으로 연산을 구현해주면 최종 출력 결과를 구할 수 있다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int a = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(br.readLine());

        long answer = 1;
        for (int i=1; i<=n-1; i++) {
            answer = (answer * m) % 1000000007;
        }

        bw.write(answer+"\n");

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

제출 결과

마무리하며

해시 함수 라는 해시맵의 개념만 가져온 굉장히 까다로운 수학 문제였다. 모듈러 연산의 법칙을 찾아본 뒤 1~2시간 정도 고민해보고, 어느정도 때려맞춰서 생각해본 뒤 인터넷을 찾아보고 내 생각이 어느정도 맞았음을 알게 되었다. 그리고는 아, 해결했다 생각했는데 난관이 하나 더 있었다. 값이 매우 커지는 경우에 대한 처리에서도 모듈러 연산을 이용하여 구해야 했으므로 결국 이 문제는 모듈러 연산에 대한 이해가 아주 많이 필요했던 문제였다. 이런 문제도 바로바로 생각하여 풀 수 있도록 많이 노력해야겠다.