문제 링크입니다: https://www.acmicpc.net/problem/1238
1238번: 파티
문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때
www.acmicpc.net
현재 알고리즘 스터디를 진행할 때 파트가 다익스트라 알고리즘과 세그먼트 트리이기 때문에 이 두 알고리즘을 중점적으로 업로드할 예정입니다.
해당 문제는 쉬운 편에 속하는 문제였습니다.
일반적인 다익스트라 알고리즘을 구현한 뒤 i 번째 마을 -> X 번째 마을, X 번째 마을 -> i 번째 마을로 가는 시간 중 제일 긴 시간을 구해주면 됩니다.
N이 최대 1000이기 때문에 알고리즘의 시간 복잡도가 2 * N^2O(logN)인데도 TLE가 발생하지 않습니다.
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 5817번 고통받는 난쟁이들 (0) | 2019.05.22 |
|---|---|
| 백준 4485번 녹색 옷 입은 애가 젤다지? (0) | 2019.05.22 |
| 백준 12116번 Uzastopni (0) | 2019.05.15 |
| 백준 12115번 Baza (0) | 2019.05.15 |
| 백준 17144번 미세먼지 안녕! (5) | 2019.05.09 |