글 읽기 - 이게 맞는 코드인지 모르겠습니다.

klimmek55 5년 전 0

a의 개수*1501⁰ + b의 개수*1501¹ + c의 개수*1501²... 이런 식으로 값을 구해서 각 경우에 값이 유일하도록 하고싶었는데요,

이러면 z 같은 경우는 1501²⁵를 곱해야되는데, long long으로 계산해서 오버플로우 때문에 값이 이상해지는데도 맞았습니다가 나옵니다.

심지어 개수를 세서 더할 때도 오버플로우가 날 수 있습니다.

테스트케이스에서 걸리는 부분이 없었던건지 1501이란 수가 우연히 괜찮았던건지 모르겠습니다.

다른 분 코드를 보니 소수를 쓰는 경우가 많던데 그 이유도 궁금합니다.

이런 경우에 수를 고르는 방법이 있나요? 아니면 아예 잘못된 풀이인가요?

#include <bits/stdc++.h>

using namespace std;

long long t[26];
vector<long long> v;

int main(){
	string a, b;
	int mx = 0;

	cin >> a >> b;

	t[0] = 1;
	for (int i = 1;i < 26;++i)
		t[i] = t[i - 1] * 1501;

	for (int i = 0, al = a.length();i < al;++i) {
		long long k = 0;
		for (int j = i;j < al;++j) {
			k += t[a[j] - 'a'];

			v.push_back(k);
		}
	}

	sort(v.begin(), v.end());

	for (int i = 0, bl = b.length();i < bl;++i) {
		long long k = 0;
		for (int j = i;j < bl;++j) {
			k += t[b[j] - 'a'];

			if (binary_search(v.begin(), v.end(), k) && mx < j - i + 1)
				mx = j - i + 1;
		}
	}

	printf("%d", mx);

	return 0;
}

wookje 5년 전 1

오버플로우는 좋은 현상은 아닌데 어차피 한 바퀴 돌아도 해시값이 유일할(할 확률이 높을)테니 큰 상관은 없겠어요

해쉬값으로 소수를 사용하는 건 중복되는 경우를 방지하고자인데

자세한 건 구글에 물어보는 게 좋겠어요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이게 맞는 코드인지 모르겠습니다.

klimmek55 5년 전 0

wookje 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말