728x90
반응형
https://www.acmicpc.net/problem/15829
이 문제는 50점 맞기는 쉽다..
문제는 문자열 길이 50이하의 테스트케이스인 Large 파트에서 점수를 얻으려면 추가로 고려해야하는 부분이 있다..ㅠㅠ
내가 이 문제 만점받느라고 좀 시간을 썼다,,^^
먼저 구글링해서 힌트를 좀 얻었다.
1. 모듈러연산의 성질
1) ( A + B ) mod M = ((A mod M) + (B mod M)) mod M
2) ( A * B ) mod M = ((A mod M) * (B mod M)) mod M
위의 성질을 적용하면 이 문제는 아래의 연산으로 변경할 수 있다.
2. long 타입
아무리 매번 모듈러 연산을 해준다지만, 길이가 길어질수록, 엄청나게 큰 숫자들이 더해질 것이다!
그리고 나의 경우는 r을 매번 곱해줘서 제곱을 구현했는데, 이때도 매번 모듈러 연산을 해주더라도 int 범위를 넘어선다,,!
이때, Math.pow연산을 쓰면 50점은 받을 수 있지만 100점은 절대 불가,, 왜냐면 Math.pow(31,49)까지 가면,, long 범위도 벗어나버림... 그래서 차라리 매번 곱해주면서 모듈러 연산을 통해 크기를 줄여줘야함~~!
그래서 r로 사용하는 변수와 sum 변수는 long 타입으로 선언해야한다!!!
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String s = br.readLine();
int prime = 1234567891;
long r=1;
long sum = 0;
for(int i=0;i<N;i++){
sum += ((s.charAt(i)-'a'+1)*r)%prime;
r = (r*31)%prime;
}
System.out.println(sum%prime);
}
}
728x90
반응형
'알고리즘 (for 코딩테스트) > 백준_자바 (Java)' 카테고리의 다른 글
[Java 자바] 백준 알고리즘 2775번 답 : 부녀회장이 될테야 (0) | 2021.09.04 |
---|---|
[Java 자바] 백준 알고리즘 1920번 답 : 수 찾기 (0) | 2021.09.04 |
[Java 자바] 백준 알고리즘 2869번 답 : 달팽이는 올라가고 싶다 (0) | 2021.09.01 |
자바 실행시간 줄이는 Tip | 자바 백준 시간초과 시 해볼만한 시도 | 자바 초보자 (0) | 2021.09.01 |
[Java 자바] 백준 알고리즘 10989번 답 : 수 정렬하기3 (0) | 2021.09.01 |
최근댓글