728x90 백준 gcd와 최단 경로 파이썬1 백준 gcd와 최단 경로 [32632] 파이썬(Python) 코드 + 해설 문제 설명정점이 1번부터 N번까지 있는 그래프가 주어진다. 두 정점 x와 y 사이에 간선이 존재하는 조건은 gcd(x,y)=1일 때이다. 즉, 서로소인 정점들 사이에 간선이 존재한다.정점 x에서 정점 y까지의 최단 경로 길이 dist(x,y)는 경로에 포함된 간선의 개수로 정의된다. 경로가 존재하지 않으면 dist(x, y) = 10^{10^{10}}으로 정의된다.정수 K가 주어질 때, 다음 조건을 만족하는 정수 x의 개수를 구해야 한다.1≤x≤Ndist(x,K)=gcd(x,K)문제 해결 방법이 문제는 각 정수 x에 대해 dist(x,K)와 gcd(x,K)를 비교하여 조건을 만족하는 x의 개수를 구하는 문제이다.그래프의 특성 분석간선의 존재 조건: 두 정점 x와 y 사이에 간선이 존재하려면 gcd.. 2024. 11. 12. 이전 1 다음 728x90
