16958번 - 텔레포트
플로이드 와샬로 풀었는데 통과가 되어서 질문 올립니다.
플로이드 와샬 알고리즘의 시간복잡도는 O(V^3)이고
이 문제의 최악의 경우 정점이 1000개 이므로
최악의 경우에 1000^3, 10억번 수행으로 시간초과가 나야하는 것이 아닌가 싶습니다.
자바 시간 보너스 덕이지 않을까요.
연산에 따라 다르지만 1초에 10억번도 가능하다고합니다.
아하 자바 시간 보너스가 넉넉하게 주어진거같네요.
그런데 1초에 대략 1억번이라고 알고있었는데 연산에 따라서 1초에 10억번이 가능한 경우도 있다는 말씀이신가요?
네 그렇습니다. 덧셈 뺄셈같은 가벼운 연산이 그렇다고 하네요.
답변해주셔서 감사합니다!!!
댓글을 작성하려면 로그인해야 합니다.
hyeon930 3년 전 1
플로이드 와샬로 풀었는데 통과가 되어서 질문 올립니다.
플로이드 와샬 알고리즘의 시간복잡도는 O(V^3)이고
이 문제의 최악의 경우 정점이 1000개 이므로
최악의 경우에 1000^3, 10억번 수행으로 시간초과가 나야하는 것이 아닌가 싶습니다.