BOJ 26008 해시해킹

문제

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

26008번: 해시 해킹

 

 

문제 접근

• 해당 문제는 해싱에 대해 묻고 있다.
• 주목해야 할 점은 해싱하는데 사용하는 해시 함수 h(P)에 대해서이다. 문제에서 제시한 해시 함수는 아래와 같다.

$$ h(P) = (P_0  \ast A^0 + P_1  \ast A^1 +   \cdots  + P_{N-1}  \ast A^{N-1}) mod M $$

• 이때 $P_0$ 을 보자 $A^0$ 이 1이 되기 때문에 해당 부분을 적절히 이용하면 $P_0$의 값을 적절히 변경함으로서 해시함수의 결과값을 변화시킬 수 있다.(나머지는 A의 값에 따라 달라지기 때문에 원하는대로 컨트롤하기가 힘들다.)
• 그렇다면 문제에서 입력받은 해시 값 $H$를 도출해낼 수 있는 $P_0$이 몇 개나 존재하는가인데 예제나 수를 해시함수에 대입하여 봄으로서 $h(P)$가 $H$가 될 수 있는 $P_0$의 값은 하나만 존재하는 것을 알 수 있다.
• 위에서 $P_0$을 변경하여 해시함수의 값을 컨트롤 할 수 있다고 서술했다. 이는 곧 나머지 $P$ 값들에 대해서는 상관없이 적절한 $P_0$을 선정하여 해시함수에 넣을 수 있다면 항상 원하는 해시 값 $H$를 얻을 수 있다.
• 따라서 $H$가 나올 수 있는 가짓수는 패스워도 문자의 종류 $M$을 $P_0$를 제외한 나머지 $P_1$부터 $P_{N-1}$까지 $N-1$개를 선택하는 경우의 수가 되며 이는 곧 $M^{N-1}$이 된다.
• 즉 답은 $M^{N-1} mod 1000000007$이 된다.

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

public class StudyCode {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 ans = 1L;

        for(int i = 0; i < N - 1; i++){
            ans = (ans * M) % 1000000007;
        }

        System.out.println(ans);
    }
}

 

 

정리

• 해당 해시함수를 적절한 $P_0$을 통해 컨트롤 할 수 있고, 입력으로 받는 해시값 $H$가 도출될 수 있는 $P_0$의 값이 하나만 존재한다는 것을 알아내는 것이 중요했다.
• 즉 입력으로 받은 값을 내는 답이 하나만 존재하며 그것만 알면 나머지 요소들은 어떠한 조합이 나와도 상관없기 때문에 경우의 수를 따져볼 때 $M$ 종류의 문자를 $N-1$번 선택하는 곱의 경우의 수를 생각하면 답을 도출할 수 있다.