목록BOJ 31226 (1)
알고리즘 일지
BOJ 31226 - 고슴도치 그래프 2
문제 링크https://www.acmicpc.net/problem/31226https://www.acmicpc.net/problem/23049 문제 풀이 임의의 점에서 최대로 이동하면 사이클에 포함된 임의의 노드의 번호를 알 수 있다. 이 번호를 v라고 하자. 개수가 N일때, 2sqrt(N)의 질의로 찾을 순 있는데 900번으로는 어케 찾는거지 ㅜ 24.3. 4 쿼리를 날릴 때 거리가 굉장히 길다. 왜 길까? 정답은 1부터 1,000,000 까지 있다. 1,000,000! 을 k라고 하자. query(v, k) = v 가 된다. 이것을 응용하는 것 아닐 까? 답이 될 수 있는 정답의 경우의 수를 적절히 압축하여 곱한뒤, 거리 쿼리를 날리고 자기 자신으로 되돌아오는 쿼리를 적절히 빨리 발견하여, 소인수 분..
알고리즘 풀이
2024. 2. 29. 20:56