26008번 : 해시 해킹

해시가 웃으면? key key key..
아 이 드립 너무 value인가..?
 
전형적인 해시와 상관 없는 수학문제. 꽤나 고생했다. 규칙성은 찾았으나 확신도 없고 구현하는 데에 애를 먹어 컨닝을 좀 했따.. 잘 하는 사람이 정말 너무 많다.. 자괴감이 든다..
 

일단 어마어마한 문제 설명을 보고 아무 생각이 들지 않았으나, 차근차근히 보고 이해..를 해보려고 노력했다.
진짜 해시 함수 구현해서 숫자 하나하나씩 계산하고 해시맵에 넣어?라는 못된 생각을 하기도 했지만.. 수의 범위와 1000000007 로 나눈 나머지를 출력하라는 걸 보고 컴퓨터가 터질 수도 있겠구나 해서 이를 갈며 공책을 꺼냈다.
대놓고 이런 복잡한 문제는 수능 수학문제처럼 규칙을 찾아내라고 말 하는 것 같다. 두드리면 열리리라..
 

대략적인 문제 설명은 이렇다. (이걸 이해하는 데에도 힘들었다..)
위와 같은 설명으로 N, M, A, H가 순서대로 들어오고, 추가로 M은 A처럼 특별 해시 함수를 만드는 중요 숫자이다.
특별 해시 함수를 만드는 법을 간략히 설명하자면
각 패스워드의 숫자를 하나씩 꺼내고, 그 숫자에 A의 '몇 번째 패스워드 숫자니? (0번째부터 시작해서)' 의 제곱을 곱한다.
각 자리수를 해당 계산법으로 모두 계산하여 더하고, 거기에 M을 나눈 나머지가 답이 되시겠다.
 
이해하기 힘들 때는 예시를 보면 된다. 첫 번째 예시인 [3, 2, 1 / 1] 에서 답은 4가 나왔는데,
여기서 나는 전체 경우의 수가 8가지인데 정답은 딱 그의 절반인 4라는 점에서 주목했다.
우연인가? 그럴 리 없지. 벌써 규칙의 희망이 보이는 것 같았지만.. 예시의 숫자는 너무 작기도 하고, 하나만으론 확정할 수 없으므로 규칙을 보충해줄 예시가 필요하다. 해서 예시의 [3, 2, 1] 에서 딱 하나만 바꾼 [3, 3, 1] 의 경우의 수를 써 보았다.
 

A는 여전히 1이므로 문제의 예시처럼 [3, 3, 1] 또한 여전히 특수한 계산을 할 필요는 없다. 1의 제곱은 1이기 때문에 각 자리수를 더해주기만 해도 계산이 된다.

윗단에 쓴 27개의 숫자들이 만들 수 있는 모든 경우의 수고, 아랫단의 27개 숫자가 각각 동일 위치의 해시 값이다.
즉, 아랫단의 숫자들이 실제 각 경우의 해시 값이며, 문제에서 진짜 물어보는 내용은 아랫단의 숫자들 중 H는 몇 번 나오냐이다.
 
신기하게도 나머지는 세로 방향이든 가로 방향이든 일정한 규칙으로 반복된다. 그건 됐고. 우리가 관심 있는 것은 그래서 H는 몇 번 반복되냐인데, 공교롭게도 경우의 수가 반복되니 각각의 해시값도 모두 동일한 개수로 나온다. (해시 값이 M으로 나눈 나머지이기 때문에 해시 값은 당연하게도 M을 포함한 M 이상의 값은 나오지 않는다.) 
 
 
오? 그렇다면 전체 경우의 수에서 0 ~ M-1 개의 숫자가 동일하게 반복되니 전체 경우의 수에서 M을 나누면 되는 거네? (라는 의심을 했고, 그것에 대한 확신은 다른 사람들의 풀이를 컨닝함으로써 완성됐다.) 즉, 각 자리에 들어올 수 있는 수는 M 개, 패스워드의 자리 수는 N 개이며,  M 이하의 나머지들 (실제 해시 값이 되는 수들) 이 M^N에서 공평하게 x개씩 반복되니, x를 구하는 방법은 M^N / M 이고, 이를 풀면 M^(N-1) 이 된다!
아이씨 뭐야 간단하네! A랑은 상관도 없는 문제였잖아?? 바로 Math의 제곱 함수인 pow(M, N-1)를 이용해서 리턴하면 가볍게...!
 

Infinity..? 아 숫자가 너무 커서 int 변수에 안 담기나보다 ㅎㅎ 그래서 문제에서 1000000007 (이하 10...07) 로 나눈 나머지를 출력하라고 했구나?ㅎㅎ 그럼 long에 담으면 간단히...!
 

실제 예제의 답안은 73352076 이다.

어 왜 답이랑 다르지..?
이것 역시 숫자가 너어어~무 커져서 long 변수에 담을 수 있는 수보다 더 커졌기 때문에 숫자가 질질 샌 것.
논리적인 해결법을 알았어도 신나서 너무 까불지 말자. 키보드도 두드려보고 코딩할 것.
 

이렇게 매 for문마다 10...07 을 나누어주면 숫자가 커졌을 때 깎아줄 수 있으므로 안전하게 long 변수에 담겨 통과할 수 있었다.
 
근데 답은 맞았으나, 매 연산마다 10...07을 나누어주는 게 연산의 낭비라는 생각이 들었다. 어차피 10...07을 넘지 않으면 하나마나한 계산인데 어마어마한 횟수의 for문을 돌 때마다 해주는 게.. 그래서  answer의 숫자가 10...07을 넘을 때만 해주면 어떨까 하는 생각이 들었다. 어차피 그런 조건 마저 연산이니까 도찐개찐인 것 같지만?
 

오? 근데 놀랍게도 시간이 아주 소폭 줄었다. 아무래도 매번 산술 연산을 하는 것보단 조금 덜 힘든가보다. 인간이 미안해..
 
 
이상으로 이번 문제도 마무리. 문제 해결 능력과 코딩 실력이 곱창난 나를 자책하기도 하면서, 한편으로는 많이 풀어 보면 쉽게 생각할 수도 있을 것 같단 생각도 든다. 컨닝할 때 모범 답안들을 좀 봤는데 너무 다들 잘 하시고 쉽게 쉽게 논리적인 해결법을 슥슥 도출해내시는 걸 보며 참 정말 많이 부족하구나 느꼈다. 진짜 열심히 살고 공부해서, 미래의 내가 오늘의 코드를 봤을 때 부끄러워서 숨고 싶을 정도로 발전하자. 여러분들도 화이팅!