글 읽기 - 이 문제 시간초과 나는 입력은 못만들까요?

wjddhfaktmxj 5년 전 2

푸신 분들을 보니까 대부분 두 엘레베이터가 연결되었는지 여부를 Naive하게 for문을 돌면서 하나하나 체크한 것 같습니다. 이 과정에서 이론상 최대 N번의 for문을 돌아야 하고 총 체크해야하는 엘레베이터 쌍은 M^2개 있으므로 그래프를 만드는데만 O(NM^2)이 걸릴 것 같습니다.

하지만 그런 케이스의 입력을 만드는 것이 쉽지는 않더라고요.

100000 100

1 2

2 2

1 2

2 2

....

이런 입력을 만들었을때 거의 1초 가까이는 가지만 시간초과를 하지는 않는 것 같습니다.

여기서 조금만 더 입력을 잘만든다면 O(NM^2)으로 그래프를 만든 풀이들을 시간초과나게끔 만들수 있지 않을까요?

chogahui05 5년 전 0

제가 이걸 잘 안 풀어봐서 모르겠는데요..

대부분 두 엘레베이터가 연결되었는지 여부를 Naive하게 for문을 돌면서 하나하나 체크한 것 같습니다.

이렇게 입력을 주면 몇몇 코드에 대해서 어떻게 동작하나요?

chogahui05 5년 전 0

아니면 어느 분이 TC 요청하신 이 케이스를 넣던지..

이론적으로.. 이런 류의 문제는 흐음.. 나이브하게 for문을 돌려서 시간초과가 안 날 이유가 하나도 없거든요.

코드를 첨부하자면 아래와 같은 식으로 M^2개의 엘레베이터 쌍에 대해서 둘이 겹치는지 여부를 최대 O(N)짜리 for문을 통해서 체크를 하고 있습니다. 물론 중간에 for문이 N번보다는 조금 돌아가고 겹치는게 나오면 바로 리턴하기는 하지만 이론상으로는 O(M^2N)의 시간복잡도를 가지는 것 같아서요. 그래서 혹시 M^2개의 엘레베이터 쌍에 대해서 저 hasEdge()함수가 대략 N번씩 돌아가는 인풋을 만들수 있지 않을까 생각했습니다. 하지만 N이 조금 커지지 않으면 거의 그런 인풋을 만드는 것이 불가능할 것 같기도 하네요 ㅠㅠ.

이런 생각을 하게된 이유는 이 문제의 출제 의도가 각 층별로 연결상태를 그래프로 만든 O(N^2)풀이가 아닌 엘레베이터끼리 연결그래프를 만든 O(M^2)풀이인 것 같은데 여기서 엘레베이터끼리 연결된 경우를 O(N)에 체크하는것이 이상해서입니다.

즐거운 성탄절 되세요!

inline bool canTake(int e, int f) {
	return f>=x[e] && (f-x[e])%y[e] == 0;
}

// O(N) ??
inline bool hasEdge(int e1, int e2) {
	for (int i=x[e1]; i<=n; i+=y[e1])
		if (canTake(e2, i)) return true;
	return false;
}

int main () {
	scanf("%d%d",&n,&m);
	for (int i=0; i<m; ++i) 
		scanf("%d%d",x+i,y+i);
	scanf("%d%d",&a,&b);
	if (a == b) {
		printf("0\n");
		return 0;
	}

    /// O(M^2 N) ???
	for (int i=0; i<m; ++i) for (int j=i+1; j<m; ++j)
		if (hasEdge(i, j)) {
			adj[i].push_back(j);
			adj[j].push_back(i);
		}
}

chogahui05 5년 전 1

맞네요. wj님 말씀대로 테케가 굉장히~ 굉~~~장히 많이 허술하네요.

https://www.acmicpc.net/board/...

이 부분에 대해서는 의견에 올렸습니다.

맞은 분들 중에서 제가 제시한 input을 넣으면 잘못된 답이 나온 경우도 상당히 많이 있었습니다.

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

문제

문제

출처

ICPC

이 문제 시간초과 나는 입력은 못만들까요?

wjddhfaktmxj 5년 전 2

chogahui05 5년 전 0

chogahui05 5년 전 0

wjddhfaktmxj 5년 전 0

chogahui05 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말