글 읽기 - 이거 int 로만 풀 수 있을거 같은데

hyjin1117 1년 전 0

long 써서 100점 맞긴 했는데

이거 int로만 해서 풀 수 있을 것 같은데

테스트 케이스로

40 짜리

aaaaaaaaaasssssssssszzzzzzzzzzkkkkkkkkkk

하면 음수 나오긴 합니다

근데 제 코드에서 왜 오버플로우 나는지 잘 모르겠어요

모듈러 연산 그때그때 해주는데

import java.util.Scanner;

public class Main
{
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		
		int n = input.nextInt();
		
		String s = input.next();
		
		final int M = 1234567891;
		
		int sum = 0;
		
		for (int i=0; i<n; i++)
		{
			int temp = s.charAt(i) - 96;
			
			int q = temp % M;
			
			for (int j=1; j<=i; j++)
			{
				q *= 31;
				q %= M;
			}
			
			sum = ((sum % M) + (q % M)) % M;
		}
		
		System.out.print(sum);
	}
}

lycoris1600 1년 전 2

그때그때 모듈러연산을 한다고 오버플로우가 발생하지 않는 것이 아닙니다.

int의 범위는 2,147,483,647까지이고,

for (int j=1; j<=i; j++)

{

q *= 31;

q %= M;

}

에서 M은 1,234,567,891이므로

q%=M은 1,234,567,890까지 가능합니다.

여기서 q*=31을 하면 38,271,604,590으로 이미 int의 표현 범위를 넘어 오버플로우가 발생하게 됩니다.

hyjin1117 1년 전 0

와우

정말 날카로운 지적이네요

그러면 int형만 써서 통과하려면

2,147,483,647 / 31 = 69273666.0323

대충 q 값이 69,273,666 넘어가면

(q * 31) % M 를

( q + q + ... + q ) % M

{ (q + q ... + q) % M + (... + q) % M } % M

이런느낌으로 또 가야되겠네여

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

문제

문제

출처

ICPC

이거 int 로만 풀 수 있을거 같은데

hyjin1117 1년 전 0

lycoris1600 1년 전 2

hyjin1117 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말