글 읽기 - long long 문법에 대한 고찰이 필요합니다.

2015136077 3년 전 0

아래와 같이 코드를 작성할 때 dp 값을 int 형으로 선언을 했습니다.

dp[N]에 대한 데이터 값이 10^6이기 때문에 int 범위를 초과하지 않는다 판단했구요.

만약 10^6 * (10^6-1)/2으로 인해서 int 범위를 초과하기 때문에 rst 값은 long long으로 선언했습니다.

하지만 해당 질문처럼 dp에 대한 배열 값을 long long으로 선언해야 한다는 점을 알게 되었는데요.

이 점이 이해가 가지않습니다.

계산 변수를 int로 해서 결과 값이 long long으로 초과된다면 계산 값이 int로 포함할 수 있는 범위의 값이라도 long long으로 선언해주어야 하는건가요?

처음 접해본 난관이라 이해가 잘 안되네요. 이제까지의 문제들은 int 값을 초과한다하더라도 계산 변수값이 int라면 int로 담아 놓고 계산 결과값만 long long으로 풀어왔는데 이 문제를 풀면서 이 부분까지 캐스팅해줘야한다고 처음 생각해보았습니다.

프로그램 내부적으로 어떻게 데이터가 들어가길래 초과가 되는건가요.

#include <iostream>
#include <vector>

//n까지 더한 값에서 m인 값의 개수
//이 dp값을 int가 아닌 long long으로 선언해야 통과가 됨.
//하지만, dp[1001]에는 10^6이하의 값만이 들어갈 수 있고, 이는 int 범위 안의 값
// 물론 rst 같은 경우는 초과가 가능하지만 rst 값은 long long으로 선언
int dp[1001];
int sum[1000001];
int N, M;

inline long long calculate() {
	long long rst = 0;
	for (int i = 0; i < M; i++) {
		if (dp[i] == 0) continue;
		rst += dp[i] * (dp[i] - 1) / 2;
	}
	return rst + dp[0];
}

int main() {
	scanf("%d %d", &N, &M);
	for (int k = 1; k <= N; k++) {
		int value;
		scanf("%d", &value);
		(sum[k] = sum[k - 1] + value) %= M;
		dp[sum[k]]++;

	}
	printf("%lli", calculate());
}

dohoon 3년 전 1

int/int하면 기본적으로 내림된 정수값이 나오는 것과 같은 원리입니다.

그런 이유로 gcd값을 통해 lcm을 구하는 경우, a/gcd*b이런 식으로 계산을 합니다.

이게 문제를 틀리는 원인이 되는 경우는 상당히 빈번하기 때문에 두 정수의 곱이 나온다면 long long 문법에 대해 고찰해 보실 필요가 있습니다.

sait2000 3년 전 2

16번 줄의 곱셈이 문제입니다. 두 int 값을 곱한 결과는 int로 계산이 되는데, 이 문제에서 저 곱셈은 int 범위를 넘어갈 수 있습니다. 아래처럼 바꾸면 아마 될 겁니다.

rst += (long long)dp[i] * (dp[i] - 1) / 2;

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

문제

문제

출처

ICPC

long long 문법에 대한 고찰이 필요합니다.

2015136077 3년 전 0

dohoon 3년 전 1

sait2000 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말