글 읽기 - 시간초과 질문 드립니다.

shoomj 7년 전 0

문제에서 주어진 두 사건 번호(a b)는 방향성 그래프로 취급해서 n*n 배열에 (a, b) 위치를 -1로 표시 했고, 이와 동시에 (b, a)를 역방향을 나타내는 1로 표시 했습니다.

이후 n*n배열에 있는 1은 무시하고 -1을 확인하면서 Floyd 알고리즘으로 이어진 경로를 모두 찾는 방식으로 구현했습니다.

Floyd 알고리즘을 사용했는데 시간 초과가 나오는군요 ㅠㅠ

접근 방법이 틀린건가요?

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int n, k;
int map[401][401], ck[401];

void init() {
	int go = 0, to = 0;
	scanf("%d", &n);
	scanf("%d", &k);

	for (int i = 0; i < k; i++) {
		scanf("%d%d", &go, &to);
		map[go][to] = -1;
		map[to][go] = 1;
	}
}

void makeMap() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (map[i][k] == -1 && map[k][j] == -1) {
					map[i][j] = -1;
					map[j][i] = 1;
				}
			}
		}
	}
}

void result() {
	int m = 0;
	int x = 0, y = 0;

	scanf("%d", &m);

	for (int i = 0; i < m; i++) {
		scanf("%d%d", &x, &y);
		if (map[x][y] == 0) {
			cout << "0" << endl;
		}
		else {
			cout << map[x][y] << endl;
		}
	}

}

int main() {
	init();
	makeMap();
	result();

	return 0;
}

zlzmsrhak 7년 전 1

출력할 때 endl을 자주 쓰는 것은 시간 효율이 매우 안좋습니다.

제가 알기로는 endl을 출력할 때 마다 버퍼를 비워주기 때문에 시간이 오래 걸리는 것으로 알고 있습니다.

shoomj 7년 전 0

음~ endl은 결과 출력 할 때 줄을 바꺼줘야하니까 어쩔수 없는거 아닌가요?

이게 채점 누르면 4%에서 움직이지 않다가 시간초로 끝나네요 ㅠ

뭐가 문제인지 갑이 안오네요 ㅠ

zlzmsrhak 7년 전 0

결과적으로 cout << endl 대신 cout << "\n"를 사용해야 합니다.

shoomj 7년 전 0

감사합니다!!

"\n"으로 바꾸니까 해결됐습니다.

많은 횟수가 아니라서 크게 걱정을 안했는데, endl과 \n의 차이가 저렇게 클줄 몰랐습니다. 시간이 104ms로 쭐었습니다.

오늘도 하나 배워갑니다!! 감사해요

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

문제

문제

출처

ICPC

시간초과 질문 드립니다.

shoomj 7년 전 0

zlzmsrhak 7년 전 1

shoomj 7년 전 0

zlzmsrhak 7년 전 0

shoomj 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말