BOJ 26008 - 해시 해킹 (Python3)

오늘 시행된 2022 홍익대학교 HI-ARC 프로그래밍 경진대회, 무려 E번 문제다.

아르바이트가 늦게 끝나서 오픈콘은 A번 문제를 폰코딩하는 데에 그쳤지만, 집에 와서 찬찬히 생각해 보니 생각보다 쉬운 문제였다.

11042번 문제와 11758번 문제처럼 방법론을 깨닫자마자 미친 듯이 하락하는 난이도의 문제는 맞다.

그러나 그 방법론을 스스로 깨닫기는 녹록치 않다. 결코.

 

그럼 본격적으로 풀이에 돌입해 보자.

그리고 그 전에, 수학적으로 조금 익숙하게 보이는 방법으로 원문을 조금 수정하였음을 알린다.

---

문제

그린닷컴의 운영자 연두는 비밀번호를 평문 그대로 저장하는 과오를 뒤로하고, 이제부터 암호에 해시 함수를 적용해 저장하려고 한다. 연두가 아는 해시 함수라고는 알고리즘 문제 풀이에 많이 사용되는 롤링 해시 함수밖에 없기 때문에 이것을 응용하여 사용하기로 했다.

그린닷컴의 비밀번호 규칙은 꽤 특이한데, 길이가 정확히 N이어야 하며, 비밀번호를 이루는 문자는 지정된 M개의 문자 중 하나여야 한다. 따라서, 사용 가능한 각 문자를 0부터 차례대로 정수에 대응시키면, 비밀번호를 길이가 N이고 모든 원소가 0 이상 M-1 이하인 배열 \(P = [P_0, P_1, \cdots, P_{N-1} ]\)로 나타낼 수 있다.

이렇게 비밀번호를 배열 P로 나타낸 후, 미리 정해진 정수 A를 이용하여 다음과 같은 해시 함수 h를 적용한다.

 \[h(P) \equiv P_0 \cdot A^0 + P_1 \cdot A^1 + ... + P_{N-1} \cdot A^{N-1} \pmod M\,\,\,\,(0 \le h(P) < M)\]

예를 들어 배열 P = [10, 30, 20], A = 7, M = 55인 경우를 생각해보자. 이 경우 \(h(P) = 10 \cdot 7^0 + 30 \cdot 7^1 + 20 \cdot 7^2 \equiv 10 + 210 + 980 \equiv 45 \pmod{55}\)이다. 여기서 \(\pmod{n}\)은 n에 대한 나머지 연산으로 \(1200 = 21 \cdot 55 + 45\)이므로 \(1200 \equiv 45 \pmod{55}\)이다. 따라서 해시값은 항상 0 이상 M-1 이하의 정수이다.

그린닷컴 관리자 계정의 비밀번호 해시값을 해킹한 재현이는, 이 해시값으로 실제 비밀번호가 뭐였는지 역추적해보려고 한다. 하지만 그린닷컴에서 사용 가능한 비밀번호는 \(M^N\)개나 있고, 이 중 과연 알아낸 해시값과 일치하는 비밀번호는 몇 개나 될지 궁금해졌다. 여러분이 이것을 대신 구해주자.

 

입력

첫째 줄에 비밀번호의 길이 N과 문자 종류의 개수 M, 정수 A가 주어진다. (1 ≤ N, M, A ≤ 5,000,000)

둘째 줄에 재현이가 알아낸 해시값 정수 H가 주어진다. (0 ≤ H < M)

 

예제 입력)

# 예제 입력 1
3 2 1
1

# 예제 입력 2
5000000 5000000 5000000
1

 

출력

주어진 해시값을 갖는 비밀번호의 개수를 출력한다. 출력하는 값이 너무 커질 수 있으므로, 이것을 \(1,000,000,007=10^9+7\)로 나눈 나머지를 출력한다.

 

예제 출력)

# 예제 출력 1
4

# 예제 출력 2
73352076

 \(h([P_0, P_1, P_2]) \equiv P_0 \cdot 1^0 + P_1 \cdot 1^1 + P_2 \cdot 1^2\equiv P_0 + P_1 + P_2 \pmod 2\)이다. 따라서 가능한 모든 비밀번호의 해시값은 다음과 같다.

\(h([0, 0, 0]) = 0\), \(h([0, 0, 1]) = 1\), \(h([0, 1, 0]) = 1\), \(h([0, 1, 1]) = 0\)

\(h([1, 0, 0]) = 1\), \(h([1, 0, 1]) = 0\), \(h([1, 1, 0]) = 0\), \(h([1, 1, 1]) = 1\)

---

내 코드

n,m,a = map(int, input().split())
print(pow(m, n-1, 1000000007))

 

뭐가 이리 간단하냐고? 말하지 않았는가. 방법론을 안다면 미친 듯이 쉬워지는 문제 중 하나라고.

당연히 \(P_1, P_2, \cdots. P_{N-1}\)을 지정하는 경우의 수는 \(M^{N-1}\)이다. 각 \(P_i\)가 0부터 M-1까지 총 M개의 값을 가질 수 있으므로.

해시 함수가 x값을 가지게 되는 \(P_0\)은, 아주 놀랍게도, 다른 \(P_i\)값이 전부 고정되어 있을 때 유일하게 정해진다.

사실 그렇게 놀랄 만한 것은 아니다. 해시 함수의 정의로부터 다음이 성립해야 하기 때문.

$$ P_0 \equiv x-(P_1A^1+P_2A^2+\cdots P_{N-1}A^{N-1}) \pmod M $$

 

따라서 앞에서 구한 \(M^{N-1}\)을 1,000,000,007로 나눈 나머지가 끝.

그냥 일일이 곱해 주면서 매 번 1,000,000,007로 나누면 십중팔구 시간초과가 날 테니 pow 함수를 잘 사용하면 끝이다.

큰 수 계산이 안 되고 모듈러 지수를 손쉽게 계산할 툴이 없는 다른 언어군은 분명 이것보다 훨씬 어려우리라.

 

이로서 26008번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.