백준 - 15829

15829. Hashing 풀이

난이도: Bronze II
문제 주소: https://www.acmicpc.net/problem/15829

문제 풀이

처음에 문제를 보고 모듈러 연산이 있음에도 어떻게 풀지를 고민하다가 숫자가 엄청 커질거 같으닌까 string이나 vector 를 이용해 수백자리 곱셈에 대응할려고 함수를 짜고있었다 근대 짜다보니 든 의문이 "이런 문제가 겨우 브론즈2일리가 없는데?" 하고 문제를 다시 고민해보닌까 그냥 매 연산에 모듈러 연산을 진행하면 숫자가 커질일이 없다는걸 한참을 고민해서야 깨달았다..... ㅋㅋ
거의 4달?5달만에 다시 시작한 알고리즘이다보니 어려운거보다 간단한걸 잊어서 쉬운문제를 어렵게 돌아가서 풀려고 하는 시도가 많은거 같다
모듈러 연산이 있다면 숫자가 커질 염려는 하지 않아도 된다는걸 기억하자...

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string>
using namespace std;

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

    int l;
    string s;
    cin >> l >> s;

    long long r = 31;
    long long m = 1234567891;
    long long hash = 0;
    long long pow_r = 1;

    for (int i = 0; i < l; i++) {
        long long a_i = s[i] - 'a' + 1;
        hash = (hash + (a_i * pow_r)) % m;
        pow_r = (pow_r * r) % m;
    }

    cout << hash;
}

---

'Algorithm > 백준' 카테고리의 다른 글

[백준] 1654 - 랜선 자르기  (0)	2026.03.13
[백준] 10989 - 수 정렬하기 3  (0)	2026.03.08
백준 - 2231  (0)	2026.03.07
백준 - 1008  (0)	2026.03.06
백준 - 3273  (0)	2024.12.26