개발/BOJ

[백준] 15829 Hashing

해싱을 적용하는 문제로, 솔직히 쉬운 축에 속하는 문제이다. 이 문제 자체에서만큼은 자료형만 무작정 키워도 100점을 맞을 수 있고, 인터넷에 찾아보면 모듈러 연산의 성질로부터 정말 쉽게 푸는 방법들이 많다. 나도 처음엔 50점만 맞아서 뭐지 하고 온갖 방법으로 시도했었고, 그중에서 인터넷에 찾아봐도 딱히 나오지 않은 방법이 하나 있어서 포스팅해보려고 한다. 이 방법은 솔직히 말하면 쓸데없이 복잡하니 심심한 사람이 아니라면 다른 블로그에서 풀이법을 찾아보길 바란다. hash값이 $(\sum_0^{L-1}{a_ir^i})\,\bmod\,M$인데, 문제에서 주어진 $L,\,r$값으로 무작정 계산하면 일반적인 int 자료형의 크기를 넘어선다. 더 큰 자료형을 써도 되겠지만, 만약 $L$이 매우 커진다면 제대로..