1219번 - 오민식의 고민
주석으로 표시해둔 벨만포드함수의 바깥쪽 반복문 조건문에 의문이있습니다.
보통 다 풀이를 보면, 노드의 수만큼 +해줘서 하시더라고요(그래서 현재 문제기준으로는 N의 최대가 50이기때문에 `for(int i=1; i<=N+50; i++)`해도 맞긴해요.
근데 쓸데없는 반복을 줄이기위해 그때그때 N값에 따라 필요한만큼만 늘려보려고했습니다.
이해가 안가는건, `i<=2*(N-1)`이 안되더라고요. `i<=2*N`은 되고요.
그런데 이론적으로 N-1번 반복하는게 모든 에지를 반복하기위한 횟수이잖아요.
그럼 그 후에 또 N-1번 반복하면 결국 모든 에지를 2번 반복하는거니까, 2*(N-1)이 들어가도 가능해야하지않나요?
확인부탁드립니다.
댓글을 작성하려면 로그인해야 합니다.
chosj1526 3년 전
주석으로 표시해둔 벨만포드함수의 바깥쪽 반복문 조건문에 의문이있습니다.
보통 다 풀이를 보면, 노드의 수만큼 +해줘서 하시더라고요(그래서 현재 문제기준으로는 N의 최대가 50이기때문에 `for(int i=1; i<=N+50; i++)`해도 맞긴해요.
근데 쓸데없는 반복을 줄이기위해 그때그때 N값에 따라 필요한만큼만 늘려보려고했습니다.
이해가 안가는건, `i<=2*(N-1)`이 안되더라고요. `i<=2*N`은 되고요.
그런데 이론적으로 N-1번 반복하는게 모든 에지를 반복하기위한 횟수이잖아요.
그럼 그 후에 또 N-1번 반복하면 결국 모든 에지를 2번 반복하는거니까, 2*(N-1)이 들어가도 가능해야하지않나요?
확인부탁드립니다.