boj 15829 Hashing c++

BOJ 15829 Hashing c++

이 문제는 크게 50점 짜리 코드와 100점 짜리 코드로 나뉜다.

해당 포스트에서는 100점 짜리 코드를 포스팅 할 것을 미리 알린다.

힌트에 적힌 말이 무엇인지 파악하는 것이 우선이다. 

 

50점 짜리와 100점 짜리 코드를 나누는 경계선은 다음의 공식을 알고 있느냐 모르느냐이다.

(아래 공식이 필요한 이유는 문제에서 L의 최대값이 50이므로 r 값이 최대 r의 49승, 즉 31의 49제곱까지 커지기 때문이다. 그 값은 무려 73자리 수이다.)

(a * b) % c 의 결과를 result라고 하면,

t = (a % c) * (b % c)
if (t > c)
    t = t % c

라는 식에 대해 t == result 라는 것

 

좀 더 구체적인 예를 들자면

아래처럼 47 과 52를 미리 곱한 뒤 31로 나눈 값이나

47을 31로 나누고 52를 31로 나눈 값을 곱해서 다시 31로 나눈 값이나 동일하다는 것이다.

 

이에 대해 좀더 원리를 알고 싶다면 아래 링크에서 '곱셈' 문제에 대한 설명을 읽어보라.

blog.encrypted.gg/943?category=773649

 

 

이를 적용해 100점 짜리 코드로 만들어보자.

# include <bits/stdc++.h>
using namespace std;

// 용량이 상당히 넉넉한 문제이므로 모든 변수가 long long.
long long L; // 첫 줄에 입력 받을 L
string alphabets; // 둘째 줄에 입력 받을 문자열.
long long M = 1234567891; // 나눠줄 수.
long long R = 31; // 문제에서 r로 주어진 값 31.

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

    long long answer = 0;

    cin >> L;
    cin >> alphabets; 

    for (long long i = 0; i < L; i++)
    {
       // alphabet에 각각의 알파벳을 저장.
        char alphabet = alphabets[i];
       // 예를 들어 alphabet이 'a'라면 1을 저장해줘야 함.
       // 'a'에서 ('a' - 1)을 빼면 1이 됨.
        alphabet -= ('a' - 1);

      // r은 최초로 31의 0제곱이니까 1을 담아줌.
        long long r = 1;
      // r의 지수만큼 곱함.
        for (int j = 1; j <= i; j++)
        {
            r *= 31;
          // 아래는 r이 너무 커지는 것 방지.
          // 앞서 설명한 원리를 적용한 것.
            if (r > M) 
                r = r % M;
        }
        answer += (long long)alphabet * r;
       // 앞서 설명한 원리 적용.
          if (answer > M)
            answer = answer % M;
    }
    cout << answer;
}

 

 

백준 15829 hashing cpp