kth990303의 코딩 블로그

UCPC 2021 예선에 나온 문제이다. 본 대회 당시, 다익스트라+dp로 뇌절쳤던 문제여서 다시 풀어보았다. https://www.acmicpc.net/problem/22358 22358번: 스키장 첫 번째 줄에 다섯 개의 정수 $N, M, K, S, T$ ($1 \le N, M \le 10^5$, $0 \le K \le 10$, $1 \le S, T \le N$) 가 주어진다. 이후 $M$ 개의 줄에 각 코스의 정보가 세 개의 정수 $a_i, b_i, t_i$ ($1 \le a_i < b_i \le N$, $1 \le t_i www.acmicpc.net AC받은 풀이를 먼저 살펴보고, 다익스트라가 안되는 이유를 포스팅하겠다. AC 풀이 N이 최대 10만이지만, 리프트 횟수가 최대 10이다. 또한, l..

UCPC 2021이 이제 한달도 남지 않았다. 이번에 나는 군생활을 하면서 알고리즘 실력을 향상시키고 여러 대회를 경험해보고 싶었기 때문에 우리 학교 알고리즘 소그룹에서 팀원을 구해 경험삼아 대회에 나가볼 사람을 구했었다. 2018년, 2019년, 2020년에 비해 이번년도에는 건국대 팀이 많이 없었다. (UCPC 참여인원 중 건국대학교 소속인 사람은 우리 팀 포함 총 4명뿐이었다.) 속상하기도 했지만, 이왕 이렇게 된거 열심히 해보자 다짐하게 되는 계기가 됐다. UCPC 본선 진출은 상위 50팀 내외이다. 이는, 아무리 못해도 최소 플레티넘 중위 문제를 해결해야 본선에 진출할 수 있다는 의미. (UCPC 2020은 서버가 터져서 거의 모든 팀을 본선으로 보내버린 예외의 경우) 나는 이번 년도에 본선진출..