시도 할 만한 방법 제안할게요.
1) 탐색 도중 N번 도시에 도착하면 바로 비용을 return 한다.
2) 그래프를 정렬한다.
3) ddp[i] = i번째 도시에 도착했을 때 최소 기름값으로 정의해서 쓸모없는 중복 방문을 줄인다.
이해가 안가는 부분은 추가 질문하셔도 됩니다.
13308번 - 주유소
1 번 같은 경우 저렇게 하면 그냥 경로가 제일 짧은 것으로 반환되여 최소 기름값이 안 나오더라고요.
2 번 같은 경우는 위상 정렬을 말하시는거 같은데 정렬해서 얻는 장점이 잘 이해가 가지 않습니다.
3 번 같은 경우 이미 코드에 적용된거 같은데 혹시 그동안 거리 누적값을 제외한 최소 기름값만 말하시는건가요?
3번은 한번 더 연구해보겠습니다.
1) 우선순위 큐에 저는 (비용, 현재 도시까지 오면서 거친 도시 중에서 최소 기름값, 현재 도시)를 넣어서 비용을 기준으로 다익스트라를 돌렸습니다.
2) 인접 리스트 형태로 그래프를 저장할 때 거리를 기준으로 정렬하면 branch prediction, 비교 횟수 감소 등의 이유로 우선순위 큐 연산에서 이득이 있습니다.
3) dp[i][j] = i도시에 도착했을 때 j원 짜리 기름을 구매했을 때 비용으로 정의하고 ddp[i] = i번 도시에서 비용과 구매했던 기름값의 최소로 정의하면 우선순위 큐에 들어가는 요소의 수를 줄일 수 있습니다.
파이썬은 1번을 적용하지 않으면 일단 모두 시간 초과가 발생했었습니다. 아래는 모두 1번이 적용된 코드입니다.
아무 것도 적용하지 않은 코드 95385159
2,3번 모두 적용한 코드 95390587
2번만 적용한 코드 95390802
3번만 적용한 코드 95390948
문제 풀었습니다!
조언 감사합니다~
댓글을 작성하려면 로그인해야 합니다.
dksh_2023010518 1년 전
시간 초과를 해결할 수 있는 방법이 있을까요?