[백준] 26008 해시해킹

문제

입력

출력

 

코드( python )

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

코드( java )

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		long answer = 1L;

		int n = sc.nextInt();
		int m = sc.nextInt();
		int a = sc.nextInt();
		int h = sc.nextInt();

		for(int i = 0; i < n-1; i ++){
			answer = (answer * m)%1000000007;
		}
        System.out.println(answer);
	}
}

우선 문제는 비밀번호의 개수인 M^N개중 주어지는 해시 값 H와 같은 비밀번호의 개수를 구하라는 것이다.

결론적으로 해시 값 H와 같은 비밀번호의 개수는 일정하다. 풀이는 아래와 같다.

숫자를 하나하나 대입하면서 생각해보면 어느정도 윤곽이 보인다.

 

자바로 풀었을 때 생긴 의문점

Q. 마지막에 1000000007을 나머지연산 해준다고 생각했는데, 반복문 안에 넣어서 나머지 연산을 진행해도 같은 결과가 나온다고 한다. 왜 그럴까?

즉, (M % 1000000007)^N-1 = M^N-1 이라는 것을 의미한다.

곱셈 중간에 나머지 연산을 해도 결과는 같다는 건데 숫자가 커서 그런지는 모르겠지만 잘 와닿지 않았다.

 

풀이

여기서 드는 의문점은 그럼 a^n = a^n mod b 가 같다는 소리냐?

mod, 즉 나머지연산은 일반적인 사칙연산 개념으로 접근하면 안된다는 것을 알아야한다. (필자도 이제 알았다)

저게 그렇다는 것은 중간에 Aab + aR = aR도 성립한단 소린데 그건 말도 안되는 소리다.

뭐 그런 이유로 곱셈 중간에 나머지 연산이 들어가도 결과는 같다는 것을 알 수 있게 되었다.

 

그런데 필자는 여기서 궁금한게 한가지 더 생겼다.

곱셈 중간에 나머지 연산이 들어가도 결과가 같다는건 알겠다.

Q. 그렇다면 덧셈 중간에 나머지 연산이 들어가도 결과는 같은가?

그건 여러분들이 계산해보길 바란다. (결론만 놓고 보면 결과는 같다)

 

나머지 연산을 반복문 내에서 진행하면 끝나고 하는것보다 시간복잡도 측면에서 손해지 않은가 라는 생각도 했었지만 제곱하다가 정수형 변수로 표현가능한 범위를 넘어서서 값이 아예 잘못나오는 것보다는 시간복잡도의 손해를 좀 보더라도 제대로된 값이 나오는게 낫다는 것을 깨달았다. 물론 그거 연산좀 한다고 시간복잡도 걸리는것도 이상한거지만;;

 

이 문제 하나에 고민도 매우 오래했고, 시간도 많이 쏟았다.

그만큼 얻은 부분도 꽤 있는것 같아 뿌듯하다. 배운 부분은 까먹지 말고 복기하도록 하자.