글 읽기 - int 의 범위와 long long의 범위 질문입니다.

his130 6년 전 0

제가 처음에 모든 for문의 i를 int 로 설정했었는데 런타임 오류가 발생했습니다.

그리고 long long 으로 바꾸었더니 AC를 받았는데요.

질문은

조건에서 N,M 이 20억이하라는 조건이 있기 때문에 int 형을 썼습니다.

그리고 for문에서는 각각 범위가 i<=N, i<=M-N, i<=M 인데

결국 i 는 int 범위를 초과하지 않는건데 왜 이런 문제가 발생하는 건가요?

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int N, M;
	long long cnt2 = 0, cnt5 = 0;

	cin >> N >> M;

	for (long long i = 2; i <= N; i *= 2)
	{
		cnt2 += N / i;
	}
	for (long long i = 2; i <= M; i *= 2)
	{
		cnt2 -= M / i;
	}
	for (long long i = 2; i <= (N - M); i *= 2)
	{
		cnt2 -= (N - M) / i;
	}

	for (long long i = 5; i <= N; i *= 5)
	{
		cnt5 += N / i;
	}
	for (long long i = 5; i <= M; i *= 5)
	{
		cnt5 -= M / i;
	}
	for (long long i = 5; i <= (N - M); i *= 5)
	{
		cnt5 -= (N - M) / i;
	}

	cout << min(cnt2, cnt5) << endl;

	return 0;
}

Green55 6년 전 1

i가 INT_MAX/2 보다 클 때 2가 곱해져 오버플로우가 되는 케이스가 생길 수 있습니다.

his130 6년 전 0

아..! for문으로 들어오지 않더라도 일단 곱해져서 오버플로우가 생긴다는 말씀이시죠??

Green55 6년 전 1

i가 오버플로우가 되면, 음수가 되는 등 20억보다 작은 숫자가 될 확률이 크겠죠. 따라서 for문을 아예 벗어나지 못할 확률도 큽니다.

실제로 아래 코드를 돌려보면 다음과 같은 결과가 나옵니다

2
4
8
...
536870912
1073741824
-2147483648
0
0
0
...

	int N = 2000000000;
	for(int i=2; i<N; i*=2)
		cout << i << endl;

his130 6년 전 0

아 그렇군요 너무 감사합니다!

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

문제

문제

출처

ICPC

int 의 범위와 long long의 범위 질문입니다.

his130 6년 전 0

Green55 6년 전 1

his130 6년 전 0

Green55 6년 전 1

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말