백준/C

백준 15829번 : Hashing [C]

대니스 2022. 8. 3. 15:30

주소 : https://www.acmicpc.net/problem/15829

 

15829번: Hashing

APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정

www.acmicpc.net

 

소스 코드 :

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define M 1234567891

int main()
{
	int len, i;
	long long hash = 0, R = 1;
	char str[51];

	scanf("%d %s", &len, str);

	for (i = 0; i < len; i++)
	{
		hash = (hash + (str[i] - 'a' + 1) * R) % M;
		R = (R * 31) % M;
	}
	printf("%d\n", hash);

	return 0;
}

마무리 : 이 문제를 처음 풀 때 계속 50점으로 나와 어떻게 풀어야할지 잘 몰랐다. 50점이 나온 이유는 숫자의 범위가 너무 커져서 100점을 받지 못하게 된 것이다. 그래서 for문 안에 있는 식을 이용해서 범위를 줄이는 대신에 답에 영향을 끼치지 않게 만든 것이다.