BOJ 12859 점프하는 민호
BOJ 12859 점프하는 민호
문제 내용
생략
문제 풀이
스포일러
수직선의 모든 점을 방문할 수 있으려면, 고른 모든 수의 GCD를 구했을 때 1이 되면 됩니다. 이제 문제는 그러한 조합 중에서 비용이 가장 작은 것을 찾는 것입니다.
이는 현재의 GCD 값을 상태(또는 정점)으로 두고, 각각의 수에서 시작하여 하나의 수를 추가해 보기를 반복하는 다익스트라 또는 DP로 구할 수 있습니다. 실제로 방문하는 정점의 수가 충분히 작다는 믿음이 필요합니다.
Last updated on