[백준/C++] 15829번 Hashing

문제: www.acmicpc.net/problem/15829

15829번: Hashing

 

 

문제풀이

 

해시가 무엇인지 배워보는 맛보기 문제이다.

 

문제의 설명대로 따라서 구현하게 되면 50점을 받게 된다.

 

100점이 요구하는 50 길이의 문자열은 31^50 으로 크기가 어마어마하게 커지게 된다.

그래서 이 문제를 풀려면 모듈러 연산의 성질을 알아야 한다.

 

모듈러 연산은 덧셈, 뺄셈, 곱셉일 때 분배 법칙이 성립한다. (나눗셈일 땐 안됨)

 

(A+B) % MOD = (A%MOD +B%MOD) % MOD

 

때문에 코드의 모든 항에 모듈러 연산을 해주면 자료형의 크기를 초과하지 않고 정답을 구할 수 있다.

 

 

 

코드

#include <iostream>

using namespace std;

#define M 1234567891 //

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);

    int L;
    cin>>L; //문자열을 string형으로 입력받아서 쓸데가 없다.

    string str;
    cin>>str;

    long long R = 1; //계수
    long long sum = 0;
    for(int i=0; i<str.size(); i++){
        sum += int(str[i]-96)*R%M; //모듈러 연산은 덧셈, 뺄셈, 곱셈일 때 분배법칙 성립
        R *= 31;
        R %= M;
    }
    cout<<sum%M;

    return 0;
}

 

 

결과