글 읽기 - 시간초과가 나는 이유를 모르겠습니다..ㅠㅠ 고수님들 도와주세요..

sourish92 5년 전 0

안녕하세요.

제목 그대로.. 시간 초과가 나는 이유를 도저히 모르겠습니다..

중간 mid값 연산 과정에서 int 범위를 넘어갈 수 있기 때문에 long long으로 타입 캐스팅을 해주고 처음 코드를 제출했더니 시간초과가 났습니다.

아무리 생각해도 O(nlgn)이라서 시간초과가 나지 않을 것 같은데 계속 코드를 수정하다가

전체를 long long 형으로 제출했더니 AC를 받았습니다. 하지만, 정답을 맞춘이후에도 아래의 코드가 왜 시간초과가 발생하는지 모르겠습니다..ㅠㅠ 이유를 아시는 고수님들 도와주시면 감사하겠습니다..ㅠㅠ

/* 정답 코드 */
#include<stdio.h>
#include<algorithm>

#define LL long long
using namespace std;

int N, K;
LL arr[10010];

int main() {
	scanf("%d %d", &N, &K);
	LL left = 1, right = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
		right = max(right, arr[i]);
	}
	LL ans = 1;
	while (left <= right) {
		LL m = (left + right) >> 1;
		LL sum = 0;
		for (int i = 0; i < N; i++)
			sum += (arr[i] / m);
		if (sum >= K) {
			left = m + 1;
			ans = max(ans, m);
		}
		else
			right = m - 1;
	}
	printf("%lld\n", ans);
}

/* 시간 초과 코드 */
#include<stdio.h>
#include<algorithm>

#define LL long long
using namespace std;

int N, K;
int arr[10010];

int main() {
	scanf("%d %d", &N, &K);
	int left = 1, right = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
		right = max(right, arr[i]);
	}
	LL ans = 1;
	while (left <= right) {
		LL m = ((LL)(left) + right) >> 1;
		LL sum = 0;
		for (int i = 0; i < N; i++)
			sum += (arr[i] / m);
		if (sum >= K) {
			left = m + 1;
			ans = max(ans, m);
		}
		else
			right = m-1;
	}
	printf("%lld\n", ans);
}

BaaaaaaaaaaarkingDog 5년 전 2

left = m+1에서 m이 0x7fffffff이면 int overflow가 발생하고, 그 overflow로 인해 left와 right의 값이 왜곡되어서 while문을 탈출하지 못하네요.

1 1 2147483647

sourish92 5년 전 0

아...mid부분이 아니라 거기서 시간초과가 나는거였군요..

정말 감사합니다 ㅜㅜ 왜때문인지 몰라서 분해가지고 잠도 못잘 뻔했어요 ㅜㅜ 정말 감사합니다ㅜㅜ 복 받으실거에요

BaaaaaaaaaaarkingDog 5년 전 1

중간중간 assert문 잘 이용하시면 원인 찾는데 도움 많이 될거에요

sourish92 5년 전 0

네!! 좋은 정보 감사합니당 ㅎㅎㅎㅎㅎㅎㅎㅎ

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

문제

문제

출처

ICPC

시간초과가 나는 이유를 모르겠습니다..ㅠㅠ 고수님들 도와주세요..

sourish92 5년 전 0

BaaaaaaaaaaarkingDog 5년 전 2

sourish92 5년 전 0

BaaaaaaaaaaarkingDog 5년 전 1

sourish92 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말