글 읽기 - int 형 long long 형

hjs12345 4년 전 0

문제의 출력값이 int형 범위 내에서 나오는대 왜 출력값을 int로 하면 틀리고 long long 으로 하면 맞더군요. 분명 이유가 있을텐대 그 이유가 저의 생각안에서는 잘 모르겠습니다. 혹시 이 이유를 알려주실수 있으실까요??

#include<iostream>
using namespace std;

const long long mod = 1000000009;
long long memo[1000001];
long long go(int n)
{
	memo[0] = 1;
	memo[1] = 1;
	memo[2] = 2;

	if (memo[n] != 0)
	{
		return memo[n];
	}
	else
	{
		memo[n] = (go(n - 1) + go(n - 2) + go(n - 3)) % mod;
	}

	return memo[n];
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int n;
	int num;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> num;
		cout << go(num) << '\n';
	}
	return 0;
}

kyo20111 4년 전 3

18번째 줄에 3개의 10⁹+9 미만의 값을 더하는데 이 값이 int를 넘어 설수 있기 때문입니다.

memo[n] = ((go(n - 1) + go(n - 2)) % mod + go(n - 3)) % mod; 이렇게 고치면 맞습니다.

hjs12345 4년 전 0

아 memo[n]에 결과적으로 저장되는 값이 int 형 범위안이어도 중간에 계산하면서 넘어가면 그렇게 되는군요. 덕분에 한가지 알아갑니다 감사함니다

sls666 3년 전 0

같은 질문이 있어 댓글을 남깁니다..

계산의 중간에 int의 범위를 넘어간다는 것은 이해하겠는데, go(n - 1) + go(n - 2) + go(n - 3) 이 경우 계산의 결과가 memo[n]에 담기기전에 int형 변수에 임시로 담기는 건가요??

int형의 연산은 int범위안에서 계산이 이루어져야 하는건지??? 내부적으로 덧셈이 어떻게 이루어지는지 궁금합니다. 찾아봐도 안 나와서요ㅜㅜ

hjs12345 3년 전 0

값이 mod로 나누어지기 전에 세 수의 합이 범위를 넘어 버리면 쓰레기 값이 나와서 그런것 같아요

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

문제

문제

출처

ICPC

int 형 long long 형

hjs12345 4년 전 0

kyo20111 4년 전 3

hjs12345 4년 전 0

sls666 3년 전 0

hjs12345 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말