https://www.acmicpc.net/problem/15829
아무생각 없이 풀고 제출했다가 50점 받고 뭐지???? 했던 문제이다.
int 대신 long 타입을 사용했음에도 불구하고 50점이 나오는데, 그 이유는 31의 제곱수를 계산할때 overflow가 나기 때문이었다. Math.pow()함수를 사용했다면 주의하도록 하자.
이를 해결하기 위해 구글링을 좀 해봤는데 모듈러 연산의 성질 중 분배법칙을 이용하면 overflow를 해결할 수 있다고 한다.
주로 큰 수로 나눈 나머지를 구하라는 문제에서, 단순히 결과값에 %를 취하기 보단 연산 과정 중에서도 %를 취해야 하는 경우가 많다고 한다.
모듈러 연산의 성질
모듈러 연산은 분배법칙이 성립한다. 아래 성질을 이용하여 코드를 짜주도록 하자.
참고로 나눗셈은 분배법칙을 적용할 수 없어서 다른 방법을 써야한다고 한다.(페르마 소정리라고 하는데 그게 뭔진 아직 공부 안함)
(A+B) mod C = (A mod C + B mod C) mod C
(A - B) mod C = (A mod C - B mod C) mod C
(A * B) mod C = (A mod C * B mod C) mod C
문제 페이지에 나와있는 수식에 덧셈의 분배법칙을 적용하여 아래와 같이 풀어보았다.
이대로 코드를 짠다면 r의 거듭제곱과정에서 overflow가 발생할 수 있기 때문에, 곱셈의 분배법칙도 적용해줘야 한다.
31%M이나 31이나 똑같다는 점을 이용해서 불필요한 %M은 생략하고 짠 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static final int M = 1234567891;
public static void main(String[] args) throws IOException {
BufferedReader bw = new BufferedReader(new InputStreamReader(System.in));
int L = Integer.parseInt(bw.readLine());
String str = new String(bw.readLine());
long sum = 0;
long pow = 1;
char[] arr = str.toCharArray();
for(int i = 0; i < L; i++)
{
sum += (arr[i] - 'a' + 1) * pow % M; //분배법칙
pow = pow * 31 % M; //분배법칙
}
long hash = sum % M;
System.out.println(hash);
}
}
'알고리즘 > BAEKJOON' 카테고리의 다른 글
[백준] 2579번 계단오르기 -C++ (0) | 2022.02.15 |
---|---|
[백준] 11729번 하노이 탑 이동 순서 -자바(JAVA) (0) | 2022.01.24 |
[백준] 4673번 셀프 넘버 -자바(JAVA) (2) | 2022.01.19 |
[백준] 10757번 큰 수 A+B -자바(JAVA) (0) | 2022.01.12 |
[백준] 1929번 소수구하기/에라토스테네스의 체 -자바(JAVA) (0) | 2022.01.08 |