글 읽기 - 이해할 수 없습니다.

h0ngjun7 9년 전 0

맞추고나서 다른 분들의 소스를 보니... 왜 동작하는 건 같은 소스인데 제 O(n) 소스는 TLE가 나는거죠?ㅠㅠ

저게 TLE가 나서 O(1)짜리로 고쳐야 AC가 뜨더라구요. 그런데 O(1)로 일반식을 적으니까 계산 도중에 long long을 벗어나서 음수부터 계산하고 양수를 뒤에 계산해줘야하는 번거로움도 있었습니다.

//O(n)
#include <cstdio>
typedef long long ll;
int n, m, x;
ll res;
int main() {
	while (scanf("%d%d", &n, &m), !(n == 0 && m == 0)) {
		res = 0;
		for (x = 1; x <= n && x <= m; x += 2) res += (ll)(n - x + 1)*(ll)(m - x + 1)*(ll)(x);
		printf("%lld\n", res);
	}
}

//O(1)
#include <cstdio>
long long res, n, m, x, t, v;
int main() {
	while (scanf("%lld%lld", &n, &m), n) {
		if (n > m) t = n, n = m, m = t;
		x = (n - 1) / 2;
		v = x*(x + 1)*(2 * x + 1) / 6;
		res = -4 * v*(n + m - 1) + (x + 1) * (2 * x*x*(x + 1) + x*(n*m - n - m) + n*m);
		printf("%lld\n", res);
	}
}

h0ngjun7 9년 전 0

위의 소스를 ACM-ICPC live archive에 제출하니까 2.5초로 AC가 뜨던데... 저기가 대회 공식 데이터를 쓰진 않는 것 같네요 :(

공식 데이터를 넣고 제 컴퓨터에서 돌리니까 7초 정도 걸리는 것으로 보아...

pichulia 9년 전 1

음...이 문제를 맞추지 못해서 함부로 테스트를 못하겠네ㅋㅋㅋㅋ

개인적인 생각입니다만... (ll)으로 int를 long long으로 캐스팅하는 부분에서 오래 걸리는것 같네용

h0ngjun7 9년 전 1

말씀하신대로 캐스팅에서 문제가 생긴거였군요ㅠㅠ

아래 소스는 AC입니당

#include <cstdio>
typedef long long ll;
int n, m, x, lim;
ll res;
int main() {
	while (scanf("%d%d", &n, &m), n) {
		if (n > m) lim = m;
		else lim = n;
		res = 0;
		for (x = 1; x <= lim; x += 2) res += (long long)(n - x + 1)*(m - x + 1)*x;
		printf("%lld\n", res);
	}
}

wookayin 9년 전 1

제가 추측하는 이유입니다.

BOJ는 32비트 CPU 를 사용하고 있는것으로 들었습니다 (아닐수도 있습니다).
요즘 도는 대부분의 리눅스 서버들 (라이브 아카이브) 은 64비트 CPU 를 사용할 겁니다.
당연한 말이지만, 하나의 레지스터에 담을 수 있는 word 길이가 다르기 때문에
64bit integer 를 다루는 데 32비트 CPU와 64비트 CPU 의 연산당 클럭 수가 다릅니다. 당연히 64비트가 빠르겠죠.
쉽게 말해 32비트에서는 int <-> long 캐스팅에 비용이 좀 비쌀 수도 있습니다...
64비트에서는 별 차이 없는것으로 알고있습니다.

자세한 설명은 http://stackoverflow.com/questions/1941826/why-is-this-faster-on-64-bit-than-32-bit 이 글을 참고해보세요.

결론.. @baekjoon 64비트로 업글좀..

wookayin 9년 전 1

위에 제가 약간 잘못된 말을 한것 같아서 정정합니다. (@baekjoon 댓글 수정 기능이 필요해요 ㅠㅠ)

연산당 클럭 수가 다르다는건 좀 잘못된 말인것 같고 (물론 그 영향도 있겠지만...)
64비트 레지스터를 사용할 수 있느냐에 따라 생성되는 기계어/어셈블리가 다른게 더 중요한 이유일것 같습니다.

로우레벨은 저도 아주 deep하게는 몰라서 여기까지만..

baekjoon 9년 전 0

저도 64비트로 옮기고 싶긴 한데... 서버를 옮기는게 무슨 복붙처럼 쉽게 되는 일이 아니라서 말이죠 ㅠㅠ

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

문제

문제

출처

ICPC

이해할 수 없습니다.

h0ngjun7 9년 전 0

h0ngjun7 9년 전 0

pichulia 9년 전 1

h0ngjun7 9년 전 1

wookayin 9년 전 1

wookayin 9년 전 1

baekjoon 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말