반응형 다익스트라1 [백준/C++] 힘세고 강한 아침 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 풀 때, query가 들어올 때마다 계산을 했다. 그랬더니 시간초과가 나서 반복되는 계산을 줄이도록 문제를 풀었다. N이 100이기 때문에 첫 언어, 중간 언어를 정해 특정 언어로 변환하는데 걸리는 최소 비용을 계산할 수 있기 때문이다. 이 경우 O(N^2 * 최소 비용을 계산하는 시간복잡도) 이므로 문제가 해결될 것이라고 생각했다. 처음에 최소 비용을 계산할 때, priority queue를 이용해 탐색하지 않은 언어 중 항상 변환 비용이 가장 낮은 언어가 앞에 오도록 코드를 구현했다. 문제는 priority queue에 삽입하는데 O(logn)의 시간복잡도가 걸리기 때문에 시간초과가 또 났다... 2024. 4. 3. 이전 1 다음 반응형
